무거운 화물 운송

Hugo Heavy는 사업을 확장하려 한다. 그는 고객이 만든 거대한 강철 크레인을 그것이 필요한 장소까지 옮겨야 하는데, 이동 경로에 있는 모든 도로가 크레인의 무게를 견딜 수 있어야 한다.

그는 도시의 모든 도로와 다리, 그리고 각 도로의 무게 제한이 표시된 지도를 가지고 있지만, 이 경로로 옮길 수 있는 크레인의 최대 무게가 얼마인지는 모른다. 이를 계산하는 것이 당신의 임무다.

도시에는 $1$번부터 $n$번까지 번호가 매겨진 $n$개의 교차로가 있다. 도로는 교차로들을 연결하며, 각 도로에는 견딜 수 있는 최대 무게가 정해져 있다. $1$번 교차로(Hugo의 위치)에서 $n$번 교차로(고객의 위치)까지 운송할 수 있는 최대 무게를 구하라. 이는 $1$번에서 $n$번으로 가는 모든 경로 중, 경로에 포함된 도로들의 무게 제한 가운데 가장 작은 값이 최대가 되도록 하는 경로의 값이다. 모든 도로는 양방향으로 통행할 수 있으며, $1$번에서 $n$번으로 가는 경로는 항상 최소 하나 존재한다고 가정한다.

첫째 줄에는 시나리오(도시 지도)의 개수가 주어진다.

각 시나리오의 첫째 줄에는 두 정수 $n$과 $m$이 주어진다. $n$은 교차로의 수($1 \le n \le 1000$), $m$은 도로의 수이다. 이어지는 $m$개의 줄에는 각각 세 정수 $a$, $b$, $w$가 주어지며, 이는 교차로 $a$와 $b$를 잇는 도로의 최대 허용 무게가 $w$($1 \le w \le 1000000$)임을 뜻한다. 두 교차로 사이에는 도로가 최대 하나 존재한다.

각 시나리오마다 Scenario #i:를 한 줄에 출력한다. 여기서 $i$는 $1$부터 시작하는 시나리오 번호이다. 그다음 줄에 $1$번 교차로에서 $n$번 교차로까지 운송할 수 있는 최대 무게를 출력한다. 연속한 두 시나리오 사이에는 빈 줄을 하나 출력한다.