Given a tree with $N$ nodes connected by $N-1$ edges, rooted at node $1$, each edge in the tree is assigned a value, which can be either positive, negative, or zero. Your task is to calculate, for each node, the smallest total sum of edge values that can be obtained on a simple path from that particular node to any leaf node in the tree.

Notes :

• A simple path is a path in a tree that does not have repeating vertices. 
• A node that does not have any child node is called a leaf node.

Input format

• The first line contains a single integer $T$, which denotes the number of test cases.
• For each test case:
  • The first line contains $N$ denoting the number of vertices in the tree.
  • The following $N-1$ lines contain 3 space-separated integers, $u$, $v$, and $w$ indicating that there is an edge between vertices $u$ & $v$, and this edge has value $w$.

Output format

For each test case, print N integers in a new line, where the $i^{th}$ integer depicts the smallest total sum of edge values that can be obtained on a simple path from the $i^{th}$ node to any leaf node in the tree.

Constraints

$1 \leq T \leq 10^5 \\ 3 \leq N \leq 10^6 \\ 1≤u,v≤N\\ -10^9≤w≤10^9 \\ \text{The sum of all values of N over all test cases doesn't exceed } 10^6$