무거운 화물 운송

시간 제한1초메모리 제한128 MB

요약

1번 교차점에서 n번 교차점까지 운반할 수 있는 최대 무게를 구한다. 경로에 있는 도로 한계 중 가장 작은 값이 최대가 되도록 한다.

난이도: 보통10점 중 5점
유형: 그래프, 최소 신장 트리, 그리디, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

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$ 번 교차로까지 운송할 수 있는 최대 무게를 출력한다. 연속한 두 시나리오 사이에는 빈 줄을 하나 출력한다.

예제3

예제 1
입력
```
1
3 3
1 2 3
1 3 4
2 3 5
```
예상 출력
```
Scenario #1:
4
```
예제 2
입력
```
1
2 1
1 2 7
```
예상 출력
```
Scenario #1:
7
```

예제 3

입력

2
2 1
1 2 1000000
5 6
1 2 3
2 3 3
1 4 2
4 5 6
3 5 5
2 5 4

예상 출력

Scenario #1:
1000000

Scenario #2:
3