CF1184E3 Daleks' Invasion (hard)

在你的帮助下，Heidi 已经制定好了陷阱布置和防御计划。然而，突然间，Doctor 从 TARDIS 里冒了出来，告诉她他已经侦查到了 Daleks 的准备情况，而且这次 Daleks 的数量比以往任何时候都多。非常时期需要非常手段，所以 Heidi 决定冒险与 Daleks 正面交锋，并且她会考虑在任意一条走廊上布置陷阱。 这意味着她再次需要你的帮助，来计算 $E_{max}(c)$ —— 即最大的 $e \le 10^9$，使得如果我们将走廊 $c$ 的能量需求改为 $e$，那么 Daleks 可能会在入侵时使用走廊 $c$ —— 这一次你需要对所有时空走廊都进行计算。

第一行：目的地数量 $n$，走廊数量 $m$（$2 \leq n \leq 10^5$，$n - 1 \leq m \leq 10^6$）。接下来的 $m$ 行，每行包含目的地 $a$、$b$ 和能量 $e$（$1 \leq a, b \leq n$，$a \neq b$，$0 \leq e \leq 10^9$）。 不会有重复的 $\{a, b\}$ 对。保证图是连通的。不能保证所有能量需求 $e$ 都不同，也不能保证最小生成树是唯一的。

输出 $m$ 行，每行一个整数，第 $i$ 行表示输入中第 $i$ 条走廊 $c_i$ 的 $E_{max}(c_i)$。

由 ChatGPT 4.1 翻译