← 返回题目列表

Codeforces · 1184/E2

E2. 戴立克的入侵(中)

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

在一次成功的现场测试后,海蒂正在考虑沿着某些走廊部署陷阱,这可能不是第一个。她想避免在时间漩涡内遇到戴立克人,因此为了谨慎起见,她考虑只在那些根据当前戴立克人的计划不会使用的走廊上放置陷阱——即使用走廊的最小生成树。海蒂知道不同走廊的所有能源需求现在都不同,而且戴立克夫妇有一个他们打算使用的独特计划。

你的任务是计算数字 $$$E_{max}(c)$$$,它的定义方式与简单版本中的相同 - 即最大的 $$$e \le 10^9$$$ 这样,如果我们将走廊 $$$c$$$ 的能量更改为 $$$e$$$,Daleks 可能会使用它 - 但现在对于海蒂考虑的每个走廊。

输入

第一行:目的地数量 $$$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-(n-1)$$$ 行,每行包含一个整数:$$$E_{max}(c_i)$$$,用于来自不属于当前 Daleks 计划(最小生成树)的输入的第 $$$i$$$ 走廊 $$$c_i$$$。

示例

输入 #1

3 3
1 2 8
2 3 3
3 1 4

输出 #1

4

注意

如果$$$m = n-1$$$,那么你不需要输出任何东西。