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 $ .

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.

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 $ .

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 $ .