Amazing Experiment

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Dr.Zero lives in Treeland. Tree land consists of a tree with N nodes connected by N1 weighted undirected edges. The nodes of the tree are numbered from 1 to N. The tree is rooted at node 1.
Dr. Zero wanted to create a super amazing experiment. Before starting the experiment, he has laid out few important definitions needed.
 A subtree rooted at node x is defined recursively. It contains node x and the nodes in the subtrees of its children nodes.
 The strategic cost of a node in the subtree is defined as the distance to the farthest node from it in the whole subtree.
 The strategic cost of a subtree is defined by the minimum of strategic cost of all the nodes in the subtree.
In the experiment, he found strategic cost of subtree of each node in the tree. Sadly, he has misplaced the paper containing those results and now seeks your help.
Input
The first line of input contains one integer T, the number of test cases.
For each test case: the first line contains N, the number of nodes.
In the next N1 lines, each line contains 3 integers u,v,w which indicates an edge between node u and v with length w.
Output
For each test case, output N lines, ith of those should contain an integer corresponding to the strategic cost of subtree rooted at vertex i.
Constraints
 1 ≤ T ≤ 50
 1 ≤ N ≤ 10^5
 1 ≤ w ≤ 10^4
Subtasks
Subtask #1 (10 points)
 1 ≤ N ≤ 100
 All edges are connected to node number 1
Subtask #2 (20 points)
 1 ≤ N ≤ 100
Subtask #3 (30 points)
 1 ≤ N ≤ 2000
Subtask #4 (40 points)
 1 ≤ T ≤ 20
 1 ≤ N ≤ 10^{5}
Example
Input: 1 6 1 2 5 1 5 6 2 3 2 2 4 1 3 6 1 Output: 8 3 1 0 0 0
Explanation
The cost of the tree rooted at vertex 1 is 8, because the vertex with the minimum strategic cost is 1 and the farthest vertex from it 6 with distance 8.
The cost of the tree rooted at vertex 2 is 3, here both vertices 2 and 3 have minimum strategic cost; the farthest vertex from 3 is 4 with distance 3 and the farthest vertex from 2 is 6 with distance 3 as well.
In the tree rooted at 3, both 3 and 6 have minimum strategic cost.
The rest of the trees are singlenode trees because they're rooted at leaves.
Author:  alex77 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/AMAEXPER 
Tags  alex77 april16 jumppointer medium tree 
Date Added:  30112015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions