問題文

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
• 与えられる無向グラフは単純かつ連結

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