Given a tree with IN 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 IN denoting the number of vertices in the tree.

The following IN$-1$ lines contain $3$ space$-$separated integers, u$,$ v$,$ and w indicating that there is an edge between vertices u & tv$,$ and this edge has value w$.$

Output format For each test case, print N integers in a new line, where the the integer depicts the smallest total sum of edge