問題文

AtCoder 社の料理長を務めるあなたはよく高橋社長に自慢のハンバーグをふるまっていますが、せっかく仕入れたパセリを高橋社長が食べてくれず困っています。そこであなたは、パセリを一箇所でカットして食べやすくすることにしました。

パセリは $N$ 頂点 $N$ 辺の単純かつ連結な無向グラフで表され、頂点にも辺にも $1$ から $N$ までの番号がついています。辺 $i$ は $2$ 頂点 $A_i, B_i$ をつないでおり、長さは $C_i$ です。

連結な頂点対 $(u, v)$ 全てに対して $u, v$ 間の最短距離を求めたとき、その最大値をパセリの 硬さ と定義します。

全ての $i\\ (1 \\leq i \\leq N)$ に対して、辺 $i$ のみを取り除いたパセリの硬さを求めてください。

制約

• 入力はすべて整数
• $3 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq A_i, B_i \\leq N$
• $1 \\leq C_i \\leq 10^9$
• 与えられる無向グラフは単純かつ連結

入力

入力は以下の形式で標準入力から与えられる。

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

出力

$N$ 行出力せよ。$i$ 行目には、辺 $i$ のみを取り除いたパセリの硬さを出力すること。

入力例 1

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

出力例 1

9
11
10
5
4

• 辺 $1$ のみを取り除いたパセリにおいて、最短距離は $(1, 5)$ 間の $9$ が最大です。
• 辺 $2$ のみを取り除いたパセリにおいて、最短距離は $(2, 5)$ 間の $11$ が最大です。
• 辺 $3$ のみを取り除いたパセリにおいて、最短距離は $(1, 5)$ 間の $10$ が最大です。
• 辺 $4$ のみを取り除いたパセリにおいて、最短距離は $(4, 5)$ 間の $5$ が最大です。
• 辺 $5$ のみを取り除いたパセリにおいて、最短距離は $(1, 4)$ 間の $4$ が最大です。

入力例 2

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

出力例 2

13
12
13
3
12
12

入力例 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

出力例 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