Problem Description

Snuke Festival 2017 is held on a tree with $N$ vertices numbered $1, 2, ..., N$. The $i$-th edge of this tree connects vertices $a_i$ and $b_i$ with happiness $c_i$.

Snuke and $N-1$ black cats are the staff. Snuke plans to set up a headquarters at some vertex and dispatch one black cat to each of the remaining $N-1$ vertices.

Calculate the goodness for all vertices when the headquarters is placed at that vertex. The goodness when the headquarters is at vertex $i$ is calculated as follows:

• Let $X=0$
• For each integer $j$ from $1$ to $N$ (excluding $i$), perform the following:
• Add the happiness $c$ of the edge with the smallest happiness on the path from vertex $i$ to vertex $j$ to $X$
• The final value of $X$ is the goodness

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ b_1 $ $ c_1 $ $ : $ $ a_{N-1} $ $ b_{N-1} $ $ c_{N-1} $

Output Format

Output $N$ lines with the answer. The $i$-th line should contain the goodness when the headquarters is placed at vertex $i$.

Sample Input and Output

Sample Input #1

3
1 2 10
2 3 20

Sample Output #1

20
30
30

Sample Input #2

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

Sample Output #2

16
20
15
14
20
15
16
20
15
20
20
20
16
15
20

Sample Input #3

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

Sample Output #3

103
237
71
263
370
193
231
207
299
358
295
299
54
368
220
220
319
237
370

Notes/Hints

Constraints

• $1 \leq N \leq 10^{5}$
• $1 \leq a_i, b_i \leq N$
• $1 \leq c_i \leq 10^{9}$
• The given graph is a tree
• All given inputs are integers

Partial Points

• For a dataset worth 200 points, $N \leq 1000$ holds
• For a dataset worth 200 points, $c_i \leq 2$ holds

Sample Explanation 1

• The following diagram shows the case when the headquarters is placed at vertices $1, 2, 3$ respectively - The number written above the edge indicates the happiness of that edge, and the number written below the vertex indicates the happiness of the edge with the smallest happiness on the path from the headquarters to that vertex

见题面 Input 部分

见题面 Output 部分