시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 512 MB54221330.952%

## 문제

Ruyi Ji has a tree where the vertices are numbered by integers from 1 to n and each edge has a weight.

For each k ≤ (n − 1), he asked you to find the largest total weight of a matching with k edges if it exists.

## 입력

The first line of input contains one integer n: the number of vertices in the tree (2 ≤ n ≤ 200 000).

Each of the next n−1 lines contains three integers ui, vi, wi, describing an edge from ui to vi with weight wi in the tree (1 ≤ ui, vi ≤ n, ui ≠ vi, −109 ≤ wi ≤ 109).

It is guaranteed that the given graph is a tree.

## 출력

Output n − 1 integers: the largest weights of the matchings with 1, 2, . . . , n − 1 edges. If there is no such matching for the current k, print “?” instead.

## 예제 입력 1

5
1 2 3
2 3 5
2 4 4
3 5 2


## 예제 출력 1

5 6 ? ?


## 예제 입력 2

10
2 8 -5
5 10 5
3 4 -5
1 6 5
3 9 5
1 7 -3
4 8 -5
10 8 -5
1 8 -3


## 예제 출력 2

5 10 15 10 ? ? ? ? ?


## 예제 입력 3

2
1 2 35


## 예제 출력 3

35


## 힌트

In the first sample, with k = 1 you should take edge (2, 3) with weight 5. And with k = 2 you should take two edges, (2, 4) and (3, 5), with total weight 6. There are no matchings with a greater number of edges

## 출처

• 문제를 만든 사람: 300iq