配点: 1100 点
問題文
作为 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