B"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 <= n <= 250 ,000 ) -- the number of vertices in Niyaz's tree. Each of the next (n - 1) lines contains three integers a , b , c ( 1 <= a, b <= n , 1 <= q c <= q 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 . "...