화물 운송

어느 지역 운송 회사가 화물 트럭으로 물건을 한 곳에서 다른 곳으로 옮기려고 합니다. 한 번 운행할 때 가능한 한 많은 화물을 운반하는 것이 목표입니다. 하지만 항상 최단 경로를 이용할 수 있는 것은 아닙니다. 일부 도로에는 (육교, 터널 등) 장애물이 있어 실을 수 있는 화물의 높이가 제한되기 때문입니다. 따라서 회사는 먼저 한 번에 최대한 많이(즉, 최대한 높이) 운반한 다음, 그 높이의 화물을 운반할 수 있는 경로들 가운데 가장 짧은 경로를 선택하려고 합니다.

주어진 화물 트럭에서 운반하는 화물의 높이를 최대로 하는 것은 운반량을 최대로 하는 것과 같습니다. 또한 안전을 위해 트럭 자체에도 넘을 수 없는 높이 제한이 있습니다.

즉, 실을 수 있는 화물의 최대 높이는 트럭의 높이 제한과, 경로에 포함된 도로들의 높이 제한 중 최솟값 가운데 더 작은 값입니다. 먼저 이 최대 높이를 구한 다음, 그 높이의 화물이 지나갈 수 있는 도로만 사용하는 최단 경로의 길이를 구하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 케이스는 공백으로 구분된 두 정수 $C$와 $R$이 한 줄에 주어지며 시작합니다. $C$는 도시의 수, $R$은 도로의 수입니다. 도시는 최대 1000개이며 1번부터 번호가 매겨집니다. 이어서 $R$개의 줄에는 각 도로가 연결하는 두 도시의 번호, 그 도로에서 허용되는 최대 높이, 그리고 그 도로의 길이가 주어집니다. 각 도로의 최대 높이는 양의 정수이며, 높이가 $-1$이면 그 도로에는 높이 제한이 없음을 뜻합니다. 각 도로의 길이는 최대 1000인 양의 정수입니다. 모든 도로는 양방향으로 통행할 수 있고, 서로 다른 두 도시를 잇는 도로는 최대 하나뿐입니다. 마지막으로 각 케이스의 마지막 줄에는 출발 도시와 도착 도시의 번호, 그리고 화물 트럭의 높이 제한(양의 정수)이 주어집니다. $C = R = 0$이면 입력이 끝납니다.

각 케이스마다 먼저 Case X:를 출력합니다. 여기서 $X$는 1부터 시작하는 케이스 번호입니다. 도착 도시에 도달할 수 있으면, 다음 줄에 maximum height = H($H$는 실을 수 있는 화물의 최대 높이), 그 다음 줄에 length of shortest route = L($L$은 최단 경로의 길이)을 출력합니다. 출발 도시에서 도착 도시에 도달할 수 없으면 Case X: 다음 줄에 cannot reach destination을 출력합니다. 서로 다른 케이스의 출력 사이에는 빈 줄을 하나 넣습니다.