Score : 800 points
Snuke Festival 2017 will be held in a tree with N vertices numbered 1,2, ...,N. The i-th edge connects Vertex a_i and b_i, and has joyfulness c_i.
The staff is Snuke and N-1 black cats. Snuke will set up the headquarters in some vertex, and from there he will deploy a cat to each of the other N-1 vertices.
For each vertex, calculate the niceness when the headquarters are set up in that vertex. The niceness when the headquarters are set up in Vertex i is calculated as follows:
Input is given from Standard Input in the following format:
N a_1 b_1 c_1 : a_{N-1} b_{N-1} c_{N-1}
Print N lines. The i-th line must contain the niceness when the headquarters are set up in Vertex i.
3 1 2 10 2 3 20
20 30 30
15 6 3 2 13 3 1 1 13 2 7 1 2 8 1 1 2 8 2 2 12 2 5 2 2 2 11 2 10 2 2 10 9 1 9 14 2 4 14 1 11 15 2
16 20 15 14 20 15 16 20 15 20 20 20 16 15 20
19 19 14 48 11 19 23 17 14 30 7 11 15 2 19 15 2 18 21 19 10 43 12 11 25 3 11 4 5 19 50 4 11 19 9 12 29 14 13 3 14 6 12 14 15 14 5 1 6 8 18 13 7 16 14
103 237 71 263 370 193 231 207 299 358 295 299 54 368 220 220 319 237 370