Problem Description

The dungeon led to a school. It seemed that the school had active club activities, so Joisino decided to observe some clubs.

In the first club she entered, a magic circle was drawn on the floor. When she inquired about what they were doing, they said they were researching other worlds. According to them, there are $ N $ worlds including this one, connected by $ N-1 $ so-called invisible borderlines, which act like gates. These worlds can travel to each other through some invisible borderlines. The invisible borderline $ i(1 ≦ i ≦ N-1) $ connects world $ A_i(1 ≦ A_i ≦ N) $ and world $ B_i(1 ≦ B_i ≦ N) $, and passing through it causes $ C_i(1 ≦ C_i ≦ 10^9) $ damage.

They seem to be looking for the world that requires the most total damage to reach from each world.

However, there are many worlds, and they seem to be having a hard time investigating. So, Joisino decided to write a program to solve this problem.

Input Format

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

$ N $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ : $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $

• The first line contains the number of worlds $ N(1 ≦ N ≦ 10^5) $.
• The next $ N-1 $ lines contain the information of each path, where the $ i $th line contains $ A_i $, $ B_i $, and $ C_i $ separated by spaces.

Output Format

The output consists of $ N $ lines. The $ i $th line should contain the number of the world that requires the most total damage to reach from the $ i $th world. If there are multiple such worlds, output the smallest number. Ensure there is a newline at the end of the output.

Sample Input and Output

Sample Input #1

3
1 2 10
2 3 15

Sample Output #1

3
3
1

Sample Input #2

5
1 2 15
1 3 15
1 4 5
4 5 10

Sample Output #2

3
7
7
3
3

Sample Input #3

10
8 3 55
9 1 160
1 4 265
9 5 571
2 9 771
4 7 818
9 10 11
2 8 569
4 6 340

Sample Output #3

None

Notes/Hints

Scoring

There are no partial points for this problem. Correctly solving it will earn you 80 points.

Sample Explanation 1

In this case, the worlds are connected as shown in the diagram below. From world $ 1 $, the most damage is taken to reach world $ 3 $ with a total of $ 25 $ damage. From world $ 2 $, the most damage is taken to reach world $ 3 $ with a total of $ 15 $ damage. From world $ 3 $, the most damage is taken to reach world $ 1 $ with a total of $ 25 $ damage.

Sample Explanation 2

In this case, the worlds are connected as shown in the diagram below. From world $ 1 $, the most damage is taken to reach world $ 2 $. From world $ 2 $, the most damage is taken to reach world $ 3 $. From world $ 3 $, the most damage is taken to reach world $ 2 $. From world $ 4 $, the most damage is taken to reach world $ 2 $. From world $ 5 $, the most damage is taken to reach world $ 2 $.

见题面 Input 部分

见题面 Output 部分