Minimum Road Closure Cost

In Surabaya city, there are \(N\) intersections numbered from \(0\) to \(N-1\) connected by \(N-1\) bidirectional roads numbered from \(0\) to \(N-2\). These roads form a tree, so there is a unique path between any two intersections. The \(i\)th road (\(0 \le i \le N-2\)) connects intersection \(U[i]\) and \(V[i]\) and closing road \(i\) costs \(W[i]\).

To promote environmental awareness, Mayor Pak Dengklek plans to host a car‐free day. To support the event, he will close some roads. He first picks a nonnegative integer \(k\) and then closes some roads so that every intersection is incident to at most \(k\) open roads. The cost to close road \(i\) is \(W[i]\).

Your task is to help Pak Dengklek compute, for every \(k\) with \(0 \le k \le N-1\), the minimum total cost to close a subset of roads such that each intersection is adjacent to at most \(k\) open roads.

You need to implement the following function:

int64[] minimum_closure_costs(int N, int[] U, int[] V, int[] W)

where:

• \(N\) is the number of intersections.
• U and V are arrays of length \(N-1\) where road \(i\) connects intersections \(U[i]\) and \(V[i]\).
• W is an array of length \(N-1\) where closing road \(i\) costs \(W[i]\).
• The function must return an array of length \(N\). For each \(k\) (\(0 \le k \le N-1\)), the \(k\)th element is the minimum total closure cost required so that each intersection remains connected to at most \(k\) open roads.

Note: Roads that are not closed remain open, and the degree of an intersection in the graph of open roads must not exceed \(k\).

inputFormat

The first line contains an integer \(N\) denoting the number of intersections. Each of the next \(N-1\) lines contains three integers \(U[i]\), \(V[i]\) and \(W[i]\) meaning that there is a road between intersections \(U[i]\) and \(V[i]\) with closing cost \(W[i]\).

outputFormat

Output \(N\) space‐separated integers. The \(k\)th integer (0-indexed) should be the minimum total cost to close roads so that every intersection has at most \(k\) open roads.

sample

3
0 1 5
1 2 10

15 5 0