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.
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 |