대역폭

컴퓨터 네트워크는 $N$대의 컴퓨터와 일부 컴퓨터 쌍을 직접 연결하는 서로 다른 $M$개의 링크로 이루어진다. 각 링크 $i$에는 대역폭 $b_i$가 연관되어 있다.

연속된 링크의 수열 $a_1, a_2, ..., a_k$에 대해, 이 수열의 대역폭은 모든 개별 링크의 대역폭 중 최솟값이다. 따라서 대역폭이 $4, 3, 1, 2$인 링크 수열의 대역폭은 1이다.

두 컴퓨터 $a$, $b$가 주어졌을 때, $B(a, b)$를 $a$와 $b$ 사이의 가능한 모든 링크 경로 중 가능한 최대 대역폭이라고 하자. 전체 컴퓨터 네트워크의 최소 대역폭은 모든 컴퓨터 쌍에 대한 $B(a, a)$의 최솟값이다. 따라서 $B(0, 1) = 1, B(1, 2) = 4, B(0, 2) = 3$이면, 최소 대역폭은 1이다.

배점

여러 테스트 케이스 그룹으로 풀이를 테스트한다. 한 그룹의 점수를 얻으려면 해당 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한 조건

$1$ |$23$| $2 \le n \le 8$, $1 \le m \le 28$

$2$ |$30$| $2 \le n \le 1\,000$, $1 \le m \le 5\,000$

$3$ |$47$| 추가 제한 조건이 없다.

입력의 첫째 줄에는 네트워크에 있는 컴퓨터와 링크의 수를 나타내는 두 정수 $1 \le N \le 10^5$와 $0 \le M \le 3 \cdot 10 ^5$가 주어진다.

다음 $M$개의 줄에는 세 정수 $0 \le a, b \le N - 1$와 $1 \le c \le 3 \cdot 10^5$가 주어지며, 이는 컴퓨터 $a$과 $b$ 사이에 대역폭이 $c$인 직접 링크가 있음을 의미한다.

입력은 항상 임의의 노드 쌍 사이에 링크로 이루어진 경로가 존재하도록 구성된다.

네트워크의 최소 대역폭을 나타내는 정수 $B$를 출력한다.