AT_past19_i.道の沈没

AtCoderLand 有 $N$ 个岛屿：岛屿 $1$、岛屿 $2$、$\ldots$、岛屿 $N$，以及 $M$ 条道路：道路 $1$、道路 $2$、$\ldots$、道路 $M$。第 $i$ 条道路连接岛屿 $A_i$ 和岛屿 $B_i$，并且是双向通行的。第 $i$ 条道路会在第 $D_i$ 天被淹没，因此在第 $D_i$ 天及之后将无法使用。

如果可以通过现有的道路在任意一对岛屿之间互相到达，那么认为这些岛屿是连通的。在第 $0$ 天（此时还没有任何道路被淹没），所有岛屿都是连通的。请找出整数 $X$，使得在第 $(X-1)$ 天岛屿依然连通，但在第 $X$ 天时变得不再连通。

输入通过标准输入给出，格式如下：

$N$ $M$
$A_1$ $B_1$ $D_1$
$A_2$ $B_2$ $D_2$
$\vdots$
$A_M$ $B_M$ $D_M$

输出答案。

样例解释 1

AtCoderLand 的岛屿如图所示：

在第 $24$ 天时，岛屿依然连通。

在第 $25$ 天，第 $2$ 条道路被淹没，例如，无法从岛屿 $1$ 到达岛屿 $2$。

因此，应当输出 $25$。

样例解释 2

可能存在连接自己岛屿的道路，也可能存在多条连接同一对岛屿的道路。

数据范围

• $2\leq N\leq 2\times 10^5$
• $N-1\leq M\leq 2\times 10^5$
• $1\leq A_i\leq B_i\leq N\ (1\leq i\leq M)$
• $1\leq D_i\leq 10^9\ (1\leq i\leq M)$
• 所有岛屿初始时是连通的。
• 所有输入值均为整数。

由 ChatGPT 5 翻译