Bandwidth

Problem ID: bandwidthTime limit: 3 secondsMemory limit: 1024 MB

Difficulty

5.3

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.

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.

 Subtask Points Limits 1 23 $2 \le n \le 8$ and $1 \le m \le 28$ 2 30 $2 \le n \le 1\, 000$ and $1 \le m \le 5\, 000$ 3 47 $2 \le n \le 100\, 000$ and $1 \le m \le 300\, 000$
Sample Input 1 Sample Output 1
3 3
0 1 1
1 2 2
2 0 2

2

Sample Input 2 Sample Output 2
4 3
0 1 10
1 2 9
2 3 10

9

Sample Input 3 Sample Output 3
4 5
0 1 15
1 2 10
2 3 15
3 0 10
0 2 15

15

Sample Input 4 Sample Output 4
4 6
0 1 6
0 2 7
0 3 4
1 2 2
1 3 9
2 3 3

6