← 返回题目列表

Codeforces · 1184/E1

E1. 戴立克的入侵(简单)

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

海蒂发现戴立克夫妇创建了一个连接不同目的地(在不同时间!)的双向时间走廊网络。 她怀疑他们正在计划对整个时空进行另一次入侵。为了对抗入侵,她计划在时间漩涡中沿着精心选择的时间走廊部署陷阱。她知道修补时间漩涡是危险的,所以她向博士咨询了如何进行。她学到了以下知识:

- 不同的时间走廊需要不同的能量来保持稳定。
- 戴立克不太可能在入侵中使用所有走廊。他们将选择一组需要最少总能量来维持的走廊,但仍然可以在任何两个目的地之间进行(时间)旅行(对于知情者:他们将使用最小生成树)。
- 设置陷阱可能会改变保持走廊稳定所需的能量。

海蒂决定进行现场测试并部署一个陷阱,将其放置在第一条走廊上。但她需要知道戴立克人在布置陷阱后是否会使用这条走廊。

她为您提供了一张时间走廊地图(无向图)以及每个走廊的能量需求。

对于走廊 $$$c$$$,$$$E_{max}(c)$$$ 是最大的 $$$e \le 10^9$$$,这样如果我们将 $$$c$$$ 所需的能量更改为 $$$e$$$,那么戴立克人在入侵中可能仍然使用 $$$c$$$(也就是说,它属于某个最小生成树)。您的任务是计算 Heidi 计划在走廊 $$$c_1$$$ 上设置陷阱的 $$$E_{max}(c_1)$$$,该走廊是图中的第一条边。

输入

第一行包含整数 $$$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_{max}(c_1)$$$,表示输入中的第一个走廊 $$$c_1$$$。

示例

输入 #1

3 3
1 2 8
2 3 3
3 1 4

输出 #1

4

注意

设置陷阱后,第一条走廊的新能源需求可能会小于、大于或等于旧的能源需求。

在示例中,如果第一个走廊的能量设置为 $$$4$$$ 或更少,则 Daleks 可以使用走廊集 $$$\{ \{ 1,2 \}, \{ 2,3 \} \}$$$ (特别是,如果它设置为小于 $$$4$$$,那么这将是他们将使用的唯一走廊集)。但是,如果它大于 $$$4$$$,那么他们将使用集合 $$$\{ \{2,3\}, \{3,1\} \}$$$。