대형 화물

Big Johnsson Trucks Inc. 는 초대형 트럭을 만드는 회사입니다. 이 회사의 최신 모델 Godzilla V12 는 너무 커서, 실을 수 있는 화물의 양이 트럭 자체의 성능 때문에 제한되는 일은 결코 없습니다. 오직 주행 경로에 놓인 도로들의 중량 제한에 의해서만 제한됩니다.

출발 도시와 도착 도시가 주어질 때, 두 도시를 잇는 경로가 여전히 존재하도록 하는 Godzilla V12 의 최대 적재량을 구하세요. 어떤 경로가 견딜 수 있는 적재량은 그 경로에 포함된 도로들의 중량 제한 중 가장 작은 값과 같으며, 경로는 자유롭게 고를 수 있습니다. 가능한 모든 경로에 대해 이 최솟값이 최대가 되는 값을 구하면 됩니다.

입력은 하나 이상의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 번째 줄에는 두 정수, 즉 도시의 수 $n$ ($2 \le n \le 200$) 과 도로 구간의 수 $r$ ($1 \le r \le 19900$) 이 주어집니다.

이어지는 $r$ 개의 줄에는 각 도로 구간이 연결하는 두 도시의 이름과 그 구간의 중량 제한이 주어집니다. 도시 이름은 최대 30자이며 공백을 포함하지 않습니다. 중량 제한은 0 이상 10000 이하의 정수입니다. 모든 도로는 양방향으로 통행할 수 있습니다.

각 테스트 케이스의 마지막 줄에는 출발 도시와 도착 도시, 두 도시의 이름이 주어집니다.

입력은 $n$ 과 $r$ 이 모두 0 인 줄로 끝나며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 두 줄을 출력합니다. 첫 줄에는 Scenario #x 를 출력하며, 여기서 $x$ 는 테스트 케이스 번호입니다 (1 부터 시작). 둘째 줄에는 y tons 를 출력하며, 여기서 $y$ 는 가능한 최대 적재량입니다. 연속한 테스트 케이스 사이는 빈 줄 하나로 구분합니다.