CF1119F.Niyaz and Small Degrees

Niyaz has a tree with $n$ vertices numerated from $1$ to $n$. A tree is a connected graph without cycles.

Each edge in this tree has strictly positive integer weight. A degree of a vertex is the number of edges adjacent to this vertex.

Niyaz does not like when vertices in the tree have too large degrees. For each $x$ from $0$ to $(n-1)$, he wants to find the smallest total weight of a set of edges to be deleted so that degrees of all vertices become at most $x$.

尼亚兹有一棵包含 $n$ 个顶点的树，顶点编号从 $1$ 到 $n$。树是一种无环的连通图。

该树中的每条边都具有严格正整数的权重。一个顶点的度数是指与该顶点相邻的边的数量。

尼亚兹不喜欢树中顶点的度数过大。对于每个从 $0$ 到 $(n-1)$ 的 $x$，他希望找出需要删除的边的最小总权重，使得所有顶点的度数均不超过 $x$。

The first line contains a single integer $n$ ($2 \le n \le 250\,000$) — the number of vertices in Niyaz's tree.

Each of the next $(n - 1)$ lines contains three integers $a$, $b$, $c$ ($1 \le a, b \le n$, $1 \leq c \leq 10^6$) — the indices of the vertices connected by this edge and its weight, respectively. It is guaranteed that the given edges form a tree.

第一行包含一个整数 $n$（$2 \le n \le 250\,000$）—— 表示尼亚兹的树中的顶点数量。

接下来的 $(n - 1)$ 行中，每行包含三个整数 $a$、$b$、$c$（$1 \le a, b \le n$，$1 \leq c \leq 10^6$）—— 分别表示该边所连接的两个顶点的编号及其权重。保证所给的边构成一棵树。

Print $n$ integers: for each $x = 0, 1, \ldots, (n-1)$ print the smallest total weight of such a set of edges that after one deletes the edges from the set, the degrees of all vertices become less than or equal to $x$.

输出 $n$ 个整数：对每个 $x = 0, 1, \ldots, (n-1)$，输出满足如下条件的边集的最小总权重——从图中删除该边集后，所有顶点的度数均不超过 $x$。

In the first example, the vertex $1$ is connected with all other vertices. So for each $x$ you should delete the $(4-x)$ lightest edges outgoing from vertex $1$, so the answers are $1+2+3+4$, $1+2+3$, $1+2$, $1$ and $0$.

In the second example, for $x=0$ you need to delete all the edges, for $x=1$ you can delete two edges with weights $1$ and $5$, and for $x \geq 2$ it is not necessary to delete edges, so the answers are $1+2+5+14$, $1+5$, $0$, $0$ and $0$.

在第一个例子中，顶点 $1$ 与所有其他顶点相连。因此，对每个 $x$，你需要删除从顶点 $1$ 出发的最轻的 $(4-x)$ 条边，故答案依次为 $1+2+3+4$、$1+2+3$、$1+2$、$1$ 和 $0$。

在第二个例子中，当 $x=0$ 时，你需要删除所有边；当 $x=1$ 时，你可以删除权重为 $1$ 和 $5$ 的两条边；而当 $x \geq 2$ 时，则无需删除任何边，故答案依次为 $1+2+5+14$、$1+5$、$0$、$0$ 和 $0$。