장거리 택시

택시 기사 나카무라는 수천 킬로미터 떨어진 도시로 가려는 손님을 태우게 되어 무척 기뻤습니다. 하지만 문제가 하나 있었습니다. 이 나라의 택시 대부분이 그렇듯, 그의 차도 휘발유보다 저렴한 액화석유가스(LPG)로 달립니다. 주유소는 5만 곳이 넘지만, 그중 LPG를 파는 곳은 1퍼센트도 되지 않습니다. 출발할 때 LPG 탱크는 가득 차 있지만 용량에 한계가 있고, 차는 1리터로 10킬로미터를 달리므로 도중에 연료를 채우지 않으면 목적지에 도착하지 못할 수도 있습니다. 그는 모든 LPG 주유소의 위치를 알고 있습니다.

현재 위치에서 목적지까지 연료가 바닥나지 않으면서 갈 수 있는 가장 짧은 경로의 길이를 구하는 프로그램을 작성하세요. 탱크 용량이 $cap$ 리터라면, 가득 채운 상태로는 다음 주유소에서 연료를 채우기 전까지 최대 $10 \times cap$ 킬로미터를 달릴 수 있습니다.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋의 형식은 다음과 같습니다.

N M cap
src dest
c(1,1) c(1,2) d(1)
c(2,1) c(2,2) d(2)
...
c(N,1) c(N,2) d(N)
s(1)
s(2)
...
s(M)

첫 줄에는 세 정수 $N$, $M$, $cap$ 이 주어집니다. $N$ ($1 \le N \le 3000$) 은 도로의 개수, $M$ ($1 \le M \le 300$) 은 LPG 주유소의 개수, $cap$ ($1 \le cap \le 200$) 은 리터 단위의 탱크 용량입니다. 다음 줄에는 출발 도시 $src$ 와 목적지 도시 $dest$ 의 이름이 주어지며, 목적지는 언제나 출발 도시와 다릅니다. 이어지는 $N$ 개의 줄은 도로를 나타냅니다. $i$ 번째 도로 ($1 \le i \le N$) 는 서로 다른 두 도시 $c_{i,1}$ 과 $c_{i,2}$ 를 정수 거리 $d_i$ ($0 < d_i \le 2000$, 킬로미터) 로 잇고, 양방향으로 오갈 수 있습니다. 서로 다른 두 도로가 같은 도시 쌍을 잇는 경우는 없으며, 각 항목은 공백 하나로 구분됩니다. 그다음 $M$ 개의 줄에는 LPG 주유소가 있는 도시들의 이름이 주어지며, 주유소가 있는 도시에는 도로가 적어도 하나 있습니다.

도시 이름은 최대 15자이며, 영문자(대소문자를 구분하는 'A'-'Z' 와 'a'-'z')만 사용합니다.

세 개의 0으로 이루어진 줄이 입력의 끝을 나타냅니다.

각 데이터셋마다, 출발 도시에서 목적지 도시까지 갈 수 있는 가장 짧은 여정의 길이(킬로미터)를 한 줄에 출력하세요. 나카무라가 목적지에 도착할 수 없다면 $-1$ 을 출력합니다. 그 밖의 다른 문자는 출력하지 마세요.

실제 탱크 용량은 보통 사양표보다 조금 더 크므로, 남은 연료가 정확히 0이 되는 순간에도 그 도시에 도착할 수 있다고 가정합니다. 또한 목적지에서는 항상 연료를 채울 수 있으므로 돌아오는 길은 고려하지 않아도 됩니다.