← 返回题目列表

AtCoder · ddcc2020_final_d

D. 帕尔/ey

中文机器翻译题面 查看原题

配点: 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