B. Save the world? Save the cat!
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Oh no! Amy the pink cat is stuck in a time loop! To save her, Rover the black cat has to make a journey to The Origin to defeat Aleph-1 the evil cat!

Define a multiverse as a network of $$$n$$$ universes numbered from $$$1$$$ to $$$n$$$, with The Origin located at node $$$1$$$. These universes are connected by a set of $$$n-1$$$ undirected tunnels, each taking $$$w_{i}$$$ time to traverse. It is guarantee that all universes belongs to the same component (in other words, a multiverse is a tree).

At the start of his journey, Rover can choose to teleport to any universe $$$s$$$. Define $$$d_{i}$$$ as the number of tunnel Rover has to traverse from universe $$$i$$$ to get to The Origin. At any point during his journey, if Rover is in universe $$$v\neq1$$$, he can perform a Super Jump and teleport to any universe $$$u$$$ such that $$$d_{u} = d_{v}$$$. Super Jump cost no time and can only be performed once during the entire journey.

Unfortunately, Rover the black cat is not good at math. Therefore, he asked you to find the minimum time needed to traverse from universe $$$s$$$ to The Origin satisfying the given constraint for every starting universe $$$s$$$ from $$$1$$$ to $$$n$$$.

Input

Each test consists of multiple test cases. The first line contains an integer t ($$$1\leq t\leq 10^{3}$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq5 \cdot 10^{5}$$$), denoting the number of universes.

Each of the following $$$n-1$$$ lines contains three integers $$$v_{i}$$$, $$$u_{i}$$$, $$$w_{i}$$$ ($$$1 \leq u_{i}, v_{i} \leq n, 1 \leq w_{i} \leq 10^{9}$$$), denoting the endpoints and the time needed to traverse the tunnel. It's guaranteed that all universes are connected via tunnels.

Output

For each testcases, print $$$n$$$ integer $$$t_{1},t_{2},\ldots,t_{n}$$$, denoting the minimum time taken to get from universe $$$i$$$ to The Origin if Rover starts his journey at universe $$$i$$$.

Example
Input
3
3
1 2 67
1 3 36
5
1 2 3
2 3 6
1 4 2
4 5 10
5
1 2 3
2 3 3
1 4 2
4 5 10
Output
0 36 36 
0 2 8 2 9 
0 2 5 2 6
Note

In the first testcase:

  • If Rover starts in universe $$$2$$$, it is optimal to perform a Super Jump from universe $$$2$$$ to universe $$$3$$$.
Rover does not necessarily need to perform a Super Jump for the rest of his starting points.

In the second testcase:

  • if Rover starts in universe $$$3$$$, it is optimal to perform a Super Jump from universe $$$2$$$ to universe $$$4$$$.
  • If Rover starts in universe $$$5$$$, it is optimal to perform a Super Jump from universe $$$5$$$ to universe $$$3$$$.
Rover does not necessarily need to perform a Super Jump for the rest of his starting points.