Problem C
Bandwidth

A computer network consists of $N$ computers with $M$ different direct links between some pairs of computers. Each link $i$ has a bandwidth $b_ i$ associated with it.

For a sequence of consecutive links $a_1, a_2, ..., a_ k$, the bandwidth of the sequence is the minimal bandwidth among all the invidual links. Thus a sequence of links with bandwidths $4, 3, 1, 2$ has bandwidth 1.

Given two computers $a$, $b$, we let $B(a, b)$ be the maximum possible bandwidth among all the possible link paths between $a$ and $b$. The minimum bandwidth of the entire computer network is the minimum of $B(a, a)$ for all pairs of computers. So if $B(0, 1) = 1, B(1, 2) = 4, B(0, 2) = 3$, the minimum bandwidth is 1.

Input

The first line of input contains two integers $1 \le N \le 100\, 000$ and $0 \le M \le 300\, 000$, the number of computers and links in the network.

The next $M$ lines contains three integers $0 \le a, b \le N - 1$ and $1 \le c \le 300\, 000$, meaning that there is a direct link between the computers $a$ and $b$ with bandwidth $c$.

The input is always constructed so that there is a path of links between any pair of nodes.

Output

You should output a single integer $B$ - the minimum bandwidth of the network.

Grading

Your solution will be graded on a number of subtasks. To get the points for a subtask, you must be accepted on all test cases in the subtask.

3 3
0 1 1
1 2 2
2 0 2

2

4 3
0 1 10
1 2 9
2 3 10

9

4 5
0 1 15
1 2 10
2 3 15
3 0 10
0 2 15

15

4 6
0 1 6
0 2 7
0 3 4
1 2 2
1 3 9
2 3 3

6