问题陈述
AtCoderLand 有 N 岛屿:岛屿 1, 岛 2, \ldots和岛屿 N, 和 M 道路:道路 1, 路 2, \ldots和道路 M。 道路 i 连接岛 A_i 和岛 B_i 双向。 道路 i\ (1\leq i\leq M) 当天将被淹没 D_i,因此当天或之后将不可用 D_i.
如果人们可以通过可用的道路在任意一对岛屿之间旅行,则称这些岛屿是相连的。 当天 0 (当没有道路被淹没时),岛屿是相连的。 求整数 X 使得岛屿在当天相连 (X-1) 但不是当天 X.
约束
- 2\leq N\leq2\times10 ^ 5
- N-1\leq M\leq2\times10 ^ 5
- 1\leq A _ i\leq B _ i\leq N\ (1\leq i\leq M)
- 1\leq D _ i\leq10 ^ 9\ (1\leq i\leq M)
- 这些岛屿最初是相连的。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A _ 1 B _ 1 D _ 1 A _ 2 B _ 2 D _ 2 \vdots A _ M B _ M D _ M
输出
打印答案。
示例输入 1
5 6 1 2 10 1 3 25 2 3 35 2 4 15 3 4 30 4 5 40
示例输出 1
25
AtCoderLand的岛屿如下图所示:

当天 24,岛屿是相连的。

当天 25, 路 2 将被淹没,从而无法在岛屿之间旅行 1 和岛 2.

因此, 25 。
示例输入 2
3 4 1 2 31 2 3 4 2 3 15 3 3 9
示例输出 2
15
可能有一条从一个岛屿通向其自身的道路,或者同一对岛屿之间有多条道路。
示例输入 3
15 20 6 7 54 5 15 63 8 14 30 5 8 52 5 9 96 1 13 51 8 13 89 4 15 81 12 12 80 4 10 48 1 11 63 1 9 72 10 14 83 3 5 30 7 12 60 1 10 60 2 11 68 5 7 52 6 12 34 1 8 41
示例输出 3
30