问题文

你是AtCoder社的料理长，经常给高桥社长端上你自己的拿手汉堡，但可恶的高桥社长从来不吃你的香菜，让你很困扰。于是你决定把香菜切碎，并让它更容易入口。

香菜用一个有 $N$ 个顶点和 $N$ 条边的简单连通无向图来表示，顶点和边都从 $1$ 到 $N$ 编号。第 $i$ 条边连接了两个顶点 $A_i$ 和 $B_i$，边的长度为 $C_i$。

对于所有连通的顶点对 $(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