Xóa cạnh đồ thị

Thành phố Quân sống là một thành phố có \(n\) quận và có \(n - 1\) con đường có trọng số nối giữa hai thành phố khác nhau, sao cho từ thành phố bất kì có thể đi sang tất cả các thành phố khác. Khi tận thế đến, có tất cả \(n - 1\) thiên thạch rơi lần lượt vào \(n - 1\) con đường theo từng thời điểm, thời điểm \(i\) thiên thạch thứ \(i\) sẽ phá hủy con đường có trọng số nhỏ nhất trong các con đường chưa bị phá hủy.

Yêu cầu : Ngay sau thời điểm thứ \(i\), có bao nhiêu cặp thành phố có thể đi lại với nhau (nói cách khác, đếm số cặp \((u, v)\) \((u < v)\), sao cho tồn tại một con đường nối giữa \(u\) và \(v\)).

Input

Dòng thứ nhất là số nguyên dương \(n\) là số thành phố \((n \leq 500000)\).

\(n - 1\) dòng tiếp theo gồm ba số \(u, v, w\) mô tả đường đi và trọng số của đường đi \((u, v \leq n, w \leq 10^9)\)

Đảm bảo trọng số của các cạnh là đôi một phân biệt.

Output

Gồm một dòng chứa \(n - 1\) số, mỗi số cách nhau một dấu cách, số thứ \(i\) mô tả kết quả ngay sau thời điểm thứ \(i\).

Example

4
1 2 3
1 3 2
1 4 1

3 1 0 

Scoring

\(20\%\) số điểm có \(n \leq 100\)

\(30\%\) số điểm có \(n \leq 1000\)

\(50\%\) số điểm còn lại không có ràng buộc gì thêm.