느린 펑크

당신은 열정적인 자전거 이용자이며 매일 집과 학교 사이를 자전거로 이동한다. 평소에는 별일 없이 집과 학교 사이의 최단 경로를 따라 자전거를 탄다. 오늘 오후 학교에서 돌아오던 중 자전거 타이어에 느린 펑크가 생긴 것을 발견했다. 타이어는 공기를 어느 정도 유지하지만 오래가지 못한다. 타이어에 공기를 채우면 일정 거리까지 자전거를 탈 수 있고, 그 후에는 타이어가 다시 펑크 나서 더 이상 자전거를 탈 수 없게 된다(그리고 당신은 자전거를 끌고 걷지 않는다).

다행히도 당신의 도시에는 마을 곳곳의 교차로에 자전거 수리소가 설치되어 있어 타이어에 다시 공기를 채우고 타이어가 펑크 날 때까지 다시 자전거를 탈 수 있다. 학교에도 수리소가 있으므로 집으로 출발하기 전에 타이어에 공기를 채울 수 있다.

당신은 타이어의 공기가 다 빠지기 전까지 얼마나 멀리 자전거를 탈 수 있는지 계산했고, 모든 교차로, 교차로 사이의 거리, 수리소의 위치를 포함한 마을의 구조를 알고 있다. 펑크 때문에 도중에 멈추지 않고 학교에서 집까지 갈 수 있는 최단 경로는 무엇인가? (타이어가 펑크 나는 순간과 정확히 같은 시각에 수리소나 집에 들어서면 멈추지 않는다.)

그림 I.1: 두 예제 입력의 그림.

입력의 첫 줄에는 네 정수 n, m, t, d가 주어지며, 2 ≤ n ≤ 500, 0 < m ≤ n(n − 1)/2, 0 < t < n, 0 < d < 231을 만족한다. n은 도시의 교차로 수, m은 도시의 도로 수, t는 수리소의 수, d는 타이어에 공기를 가득 채운 상태에서 타이어가 다시 펑크 나기 전까지 자전거를 탈 수 있는 거리이다. 교차로는 1부터 n까지 번호가 매겨져 있다. 학교는 교차로 1에, 집은 교차로 n에 있다.

입력의 둘째 줄에는 2 이상 n − 1 이하의 값을 가지는 t개의 정수가 주어진다. 이는 수리소가 위치한 교차로이다(학교의 수리소는 제외). 이 줄의 모든 정수는 서로 다르다.

다음 m개의 줄은 마을의 도로를 나타낸다. 각 줄에는 세 정수 i, j, k가 주어지며, 1 ≤ i < j ≤ n, 0 < k < 231을 만족한다. 이 세 정수는 교차로 i에서 교차로 j로 이어지는 길이 k의 직접 도로가 있음을 나타낸다. 도로는 양방향으로 이동할 수 있다. 두 교차로 사이에는 도로가 최대 하나만 존재한다.

펑크 때문에 도중에 멈추지 않고 학교에서 집까지 이동하는 데 필요한 최소 총 거리를 출력한다. 이동이 불가능하면 대신 한 줄에 stuck이라는 단어를 출력한다.

이동이 가능한 경우 최소 거리 D가 0 < D < 231을 만족함이 보장된다.

첫 번째 예제 입력에서 타이어에 펑크가 없다면 집까지의 최단 경로의 거리는 9이며, 학교에서 교차로 3과 5를 거쳐 간다. 그러나 펑크 때문에 타이어를 다시 채우기 전까지 거리 4만 이동할 수 있어, 교차로 2와 5의 수리소를 이용해야 하며 총 거리는 12가 된다.

두 번째 예제 입력에서 타이어에 펑크가 없다면 집까지의 최단 경로의 거리는 12이다. 그러나 타이어가 거리 10까지만 버티므로, 도중에 타이어가 펑크 나지 않는 경로가 없다. 교차로 2의 수리소를 이용하더라도 집이나 교차로 5의 수리소에 도달하기 전에 멈추게 된다.