Background

Original problem link: https://oier.team/problems/X3F.

"If, if, if it really could be like that, that would be nice."

Thinking back on each choice she made, Lingluo sometimes wonders whether she once had a better chance.

But since everything has already turned out this way, there is no other path except moving forward.

No matter what the result is, accept it, learn the lesson, and then... strive for a better future.

So, what should be done now is probably to avoid, as much as possible, the worst outcome that might come later.

"Avoid risks. Keep your feet on the ground. Make the choice that is most likely to work."

"It must be.".

Problem Description

You are given a rooted weighted tree with nodes numbered $1 \sim n$. The root is node $1$, and all edge weights are positive integers.

A decomposition of this tree is defined as follows: for each node, choose some of its children (you may choose all or none) as heavy children. The edge between a heavy child and its parent is called a heavy edge. Edges that are not heavy edges are called light edges.

A decomposition is $\textbf{\textit{i--}}$heavy if and only if, for every node, the number of its heavy children is at most $i$.

A decomposition is $\textbf{\textit{j--}}$light if and only if, for every simple path starting from the root (node $1$), the sum of the weights of the light edges on that path is at most $j$.

For $i = 0, 1, \cdots, n - 1$, find the minimum $j$ such that there exists an $\textit{i--}$heavy decomposition that is $\textit{j--}$light.

Input Format

The first line contains a positive integer $n$, representing the size of the tree.

The next $n - 1$ lines each contain three positive integers $u_i, v_i, w_i$, indicating that there is an edge of weight $w_i$ between nodes $u_i$ and $v_i$.

Output Format

Output one line containing $n$ integers, representing the answers for $i = 0, 1, 2, \cdots, n - 1$.

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

2 1 0 0 0

24
15 4 25
5 11 8
23 13 14
15 6 12
21 14 22
21 12 5
1 9 30
6 19 20
18 7 4
4 5 16
9 23 5
6 22 9
12 20 23
2 24 18
6 2 5
16 21 9
14 18 9
14 8 5
23 17 18
1 16 22
15 3 26
1 10 3
10 15 9

66 28 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

10
4 8 407414868
3 9 875245582
10 3 548046335
2 8 163333320
7 5 320544242
5 3 504767824
6 7 431834202
9 4 639504669
9 1 968451452

3100843302 639504669 0 0 0 0 0 0 0 0

Hint

[Sample Explanation #1]

For Sample 1, the tree is shown below:

When $i = 0$, there is only one possible decomposition: there are no heavy children or heavy edges. The simple path starting from the root with the maximum sum of light-edge weights is $1\textit{---}2\textit{---}4$, and the sum of edge weights is $2$.

When $i = 1$, you can use the decomposition shown in the figure, where the bold nodes (except the root) are heavy children. The simple path starting from the root with the maximum sum of light-edge weights is $1\textit{---}2\textit{---}5$, and the sum of light-edge weights is $1$.

When $i \ge 2$, you can make all non-root nodes heavy children. Then any simple path starting from the root that passes through the most light edges can only pass through $0$ light edges, so the maximum sum of light-edge weights is $0$.

[Sample Explanation #2]

When $i \ge 3$, you can make all non-root nodes heavy children. Then any simple path starting from the root that passes through the most light edges can only pass through $0$ light edges, so the maximum sum of light-edge weights is $0$.

When $i = 0, 1, 2$, I have a very concise explanation, but this space is too small to write it down.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le n \le 2\times10^5$, $1 \le w_i \le 10^9$, and the input is guaranteed to be a tree.

Translated by ChatGPT 5