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 翻译