← 返回题目列表

AtCoder · past19_i

I. 道路下沉

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

问题陈述

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