AT_ddcc2020_final_d Pars/ey

你作为 AtCoder 社的主厨，经常为高桥社长奉上你自豪的汉堡排，但你苦恼于高桥社长总是不吃你精心采购的欧芹。于是你决定将欧芹在某一处切开，使其更易入口。 欧芹可以用一个有 $N$ 个顶点、$N$ 条边的简单且连通的无向图来表示，顶点和边都编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$，长度为 $C_i$。 对于所有连通的顶点对 $(u, v)$，定义 $u$ 到 $v$ 的最短距离中的最大值为欧芹的**硬度**。 请你对于每一个 $i\ (1 \leq i \leq N)$，求出仅去除第 $i$ 条边后的欧芹的硬度。

输入以以下格式从标准输入读入。 > $N$ > $A_1$ $B_1$ $C_1$ > $A_2$ $B_2$ $C_2$ > $\vdots$ > $A_N$ $B_N$ $C_N$

输出 $N$ 行。第 $i$ 行输出仅去除第 $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 - 去除第 $1$ 条边后的欧芹，最短距离的最大值为 $9$，对应顶点对为 $(1, 5)$。 - 去除第 $2$ 条边后的欧芹，最短距离的最大值为 $11$，对应顶点对为 $(2, 5)$。 - 去除第 $3$ 条边后的欧芹，最短距离的最大值为 $10$，对应顶点对为 $(1, 5)$。 - 去除第 $4$ 条边后的欧芹，最短距离的最大值为 $5$，对应顶点对为 $(4, 5)$。 - 去除第 $5$ 条边后的欧芹，最短距离的最大值为 $4$，对应顶点对为 $(1, 4)$。 由 ChatGPT 4.1 翻译