L. Las Chivas de Milito
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Miguel and Misael have a weighted tree with $$$n$$$ vertices. They are very proud of their tree and believe that its structure is already perfect. Aaron, however, disagrees. He thinks that the tree would be better if its connected components had smaller diameters, so he decides to modify it by removing some of its edges. For each integer $$$k$$$ from $$$1$$$ to $$$n-1$$$, Aaron wants to remove exactly $$$k$$$ edges from the tree. After doing so, the tree is divided into $$$k+1$$$ connected components.

The diameter of a connected component is the maximum distance between any pair of its vertices, where the distance between two vertices is the sum of the weights of the edges on the unique path connecting them. The diameter of the resulting forest is defined as the maximum diameter among all its connected components.

For every $$$k$$$ from $$$1$$$ to $$$n-1$$$, determine the minimum possible diameter of the resulting forest that Aaron can obtain after removing exactly $$$k$$$ edges.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2000$$$) — the number of vertices of the tree.

Each of the next $$$n-1$$$ lines contains three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \le u, v \le n$$$ and $$$1 \le w \le 10^9$$$), indicating that there is an edge between vertices $$$u$$$ and $$$v$$$ with weight $$$w$$$.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, print a single line containing $$$n-1$$$ integers. The $$$k$$$-th integer must be the minimum possible diameter of the resulting forest after removing exactly $$$k$$$ edges, for every $$$1 \le k \le n-1$$$.

Example
Input
5
2
1 2 7
3
1 2 4
2 3 6
4
1 2 3
1 3 5
1 4 2
5
1 2 2
2 3 2
3 4 2
4 5 2
6
1 2 4
1 3 1
3 4 7
3 5 3
5 6 2
Output
0
4 0
5 2 0
4 2 2 0
10 5 2 1 0