질의 자전거 여행 경로

질은 해마다 두 마을 사이를 자전거로 여행한다. 두 마을을 잇는 경로는 여러 가지지만, 질이 달리려는 거리에는 상한이 있다. 마을과 마을을 잇는 도로가 그려진 지도와 각 도로의 거리가 주어지면, 질은 자신의 거리 조건을 만족하는 경로를 모두 알고 싶어 한다. 이런 경로를 거리가 짧은 것부터 차례로 나열하는 프로그램을 작성하라.

다음을 가정한다.

• 두 마을을 잇는 도로는 많아야 하나이며, 이 도로는 양방향이고 거리는 0보다 크다.
• 어떤 마을에서 출발해 그 마을로 곧바로 돌아오는 도로는 없다.
• 질은 편도 여행만 생각한다. 출발한 마을로 돌아오는 것은 고려하지 않는다.
• 질은 한 번의 여행에서 같은 마을을 두 번 방문하지 않는다.
• 질이 달리는 거리는 아무리 길어도 9999를 넘지 않는다.

입력에는 여러 개의 경우가 들어 있다. 각 경우는 지도, 출발 마을과 도착 마을, 질이 달릴 최대 거리로 이루어진다.

각 경우는 공백이나 줄바꿈으로 구분된 정수의 나열로 주어진다. 정수의 순서와 뜻은 다음과 같다.

• NV: 지도에 있는 마을의 수이다. 20을 넘지 않는다.
• NR: 지도에 있는 도로의 수이다. 각 도로는 서로 다른 두 마을을 잇는다.
• 도로마다 하나씩 주어지는 NR개의 삼중항 C1, C2, DIST. C1과 C2는 그 도로가 잇는 두 마을이고, DIST는 그 도로의 거리이다.
• SV, DV: 출발 마을과 도착 마을의 번호이다. 마을에는 1번부터 NV번까지 번호가 붙어 있고, SV와 DV는 서로 다르다.
• MAXDIST: 질이 편도로 달릴 최대 거리이다.

마지막 경우의 데이터 다음에는 정수 -1이 하나 주어진다.

각 경우마다 첫 줄에 Case k:를 출력한다. k는 1부터 세는 경우 번호이다. 그다음 줄부터 질이 갈 수 있는 경로를 한 줄에 하나씩, 경로의 길이를 앞에 붙여 출력한다. 경로는 길이가 짧은 것부터 출력하고, 길이가 같으면 마을 번호를 앞에서부터 차례로 비교해 작은 쪽을 먼저 출력한다.

경로 한 줄은 공백 하나로 시작해 경로의 길이와 콜론을 붙이고, 그 뒤에 마을 번호마다 공백 하나와 번호를 이어 붙인다. 길이가 4이고 마을 1, 2, 3을 지나는 경로는 4: 1 2 3으로 출력한다.

조건을 만족하는 경로가 하나도 없으면 앞에 공백 하나를 붙여 NO ACCEPTABLE TOURS를 출력한다.

연속한 두 경우의 출력 사이에는 빈 줄을 하나 넣는다.