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.

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.

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

Download the sample data files

Author: Johan Sannemo. Source: Programmeringsolympiadens träning 2015. License: Creative Commons License (cc by-sa)