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 \)