Problem Description

As the head chef at AtCoder Inc., you often serve your proud hamburgers to President Takahashi. However, you are troubled because President Takahashi does not eat the parsley you carefully sourced. Therefore, you decided to cut the parsley in one place to make it easier to eat.

The parsley is represented by a simple, connected undirected graph with $ N $ vertices and $ N $ edges, where both vertices and edges are numbered from $ 1 $ to $ N $. Edge $ i $ connects two vertices $ A_i $ and $ B_i $ with a length of $ C_i $.

The hardness of the parsley is defined as the maximum shortest distance between any connected pair of vertices $ (u, v) $.

For each $i\ (1\ \leq\ i\ \leq\ N)$, find the hardness of the parsley after removing only edge $ i $.

Input Format

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

$ N $ $ A_1 $ $ B_1 $ $ C_1 $ : $ A_{N} $ $ B_{N} $ $ C_{N} $

Output Format

Output $ N $ lines. The $ i $-th line should contain the hardness of the parsley after removing only edge $ i $.

Sample Input and Output

Sample Input #1

5
1 2 2
2 3 2
3 1 3
3 4 1
4 5 5

Sample Output #1

9
11
10
5
4

Sample Input #2

6
1 2 1
2 3 1
3 1 1
1 4 10
2 5 1
3 6 1

Sample Output #2

13
12
13
3
12
12

Sample Input #3

30
14 4 848722274
18 12 171265658
8 4 511894372
25 11 330929651
23 19 418973258
22 4 817877182
13 23 222674219
22 16 413782819
29 5 544392908
7 17 144238161
13 27 923626020
24 22 304070169
24 28 791071873
4 27 156167139
21 15 120681393
27 25 59605316
1 2 200687466
5 20 908000896
4 17 52288616
16 30 835920548
30 6 290694093
5 13 650921045
18 13 427412075
24 23 817018683
26 10 693688408
21 16 636579751
15 2 946903174
11 3 261890778
5 9 131214588
20 10 834590409

Sample Output #3

6749598432
6749598432
6749598432
6749598432
6749598432
6749598432
7303505702
5015716191
6749598432
6749598432
6749598432
7303505702
6749598432
6749598432
5971361289
6749598432
6548910966
4857711627
6749598432
6749598432
6749598432
4261075407
6749598432
7303505702
6055910024
5971361289
5971361289
6749598432
6749598432
5221319615

Notes/Hints

Constraints

• All inputs are integers.
• $3\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_i,\ B_i\ \leq\ N$
• $1\ \leq\ C_i\ \leq\ 10^9$
• The given undirected graph is simple and connected.

Sample Explanation 1

• After removing only edge $ 1 $, the maximum shortest distance is $ 9 $ between vertices $(1,\ 5)$.
• After removing only edge $ 2 $, the maximum shortest distance is $ 11 $ between vertices $(2,\ 5)$.
• After removing only edge $ 3 $, the maximum shortest distance is $ 10 $ between vertices $(1,\ 5)$.
• After removing only edge $ 4 $, the maximum shortest distance is $ 5 $ between vertices $(4,\ 5)$.
• After removing only edge $ 5 $, the maximum shortest distance is $ 4 $ between vertices $(1,\ 4)$.

见题面 Input 部分

见题面 Output 部分