I - Submerge Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

AtCoder 国には島 1, 島 2,\ldots, 島 N の N 個の島があります。 また、AtCoder 国には道 1, 道 2,\ldots, 道 M の M 本の道があり、道 i は島 A _ i と島 B _ i を双方向に結んでいます。 道 i\ (1\leq i\leq M) は D _ i 日に沈んでしまうため、D _ i 日以降に道 i を利用することはできません（D _ i 日にも利用できません）。

どの 2 つの島もいくつかの利用可能な道を使って行き来できることを、すべての島が連結であるということにします。 0 日には（つまり、どの道も沈んでいないときには）、すべての島は連結です。 X-1 日にはすべての島が連結であるが、X 日にはそうでないような整数 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

AtCoder 国の島は以下の図のようになっています。

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

Problem Statement

AtCoderLand has N islands: island 1, island 2, \ldots, and island N, and M roads: road 1, road 2, \ldots, and road M. Road i connects island A_i and island B_i bidirectionally. Road i\ (1\leq i\leq M) will be submerged on day D_i, so it will not be available on or after day D_i.

The islands are said to be connected if one can travel between any pair of islands via available roads. On day 0 (when no road is submerged), the islands are connected. Find the integer X such that the islands are connected on day (X-1) but not on day X.

Constraints

  • 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)
  • The islands are initially connected.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A _ 1 B _ 1 D _ 1
A _ 2 B _ 2 D _ 2
\vdots
A _ M B _ M D _ M

Output

Print the answer.

Sample Input 1

5 6
1 2 10
1 3 25
2 3 35
2 4 15
3 4 30
4 5 40

Sample Output 1

25

The islands of AtCoderLand are illustrated in the figure below:

On day 24, the islands are connected.

On day 25, road 2 will be submerged, making it impossible to travel between, for instance, island 1 and island 2.

Thus, 25 should be printed.

Sample Input 2

3 4
1 2 31
2 3 4
2 3 15
3 3 9

Sample Output 2

15

There may be a road that leads from an island to itself, or multiple roads between the same pair of islands.

Sample Input 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

Sample Output 3

30