# Bandwidth

#### Difficulty

5.3A 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