在你的帮助下,海蒂制定了陷阱布置和防御计划。然而突然,博士从塔迪斯中跳出来,告诉她他已经监视了戴立克的准备工作,而且数量比以往任何时候都多。绝望的时刻需要绝望的措施,因此海蒂将冒着与戴立克家族会面的风险,她会考虑在任何走廊上设置陷阱。
这意味着她再次需要你的帮助来计算 $$$E_{max}(c)$$$ – 最大的 $$$e \le 10^9$$$ 这样,如果我们将 $$$c$$$ 的能量需求更改为 $$$e$$$,那么戴立克人可能会在入侵中使用 $$$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$$$ 行,每行包含一个整数:$$$E_{max}(c_i)$$$,表示来自输入的第 $$$i$$$ 走廊 $$$c_i$$$。
示例
输入 #1
3 3 1 2 8 2 3 3 3 1 4
输出 #1
4 8 8