Long Distance Taxi

A taxi driver named Nakamura is thrilled to pick up a passenger heading to a city thousands of kilometers away. But there is a catch. Like most taxis in the country, his car runs on liquefied petroleum gas (LPG) because it is cheaper than gasoline. There are more than 50,000 gas stations, yet fewer than one percent of them sell LPG. His LPG tank starts out full, but its capacity is limited and the car travels 10 kilometers per liter, so he may not reach the destination without refilling along the way. He knows the location of every LPG station.

Write a program that finds the shortest possible route from the starting city to the destination without ever running out of gas. With a tank capacity of $cap$ liters, a full tank lets the car travel at most $10 \times cap$ kilometers before it must refuel at an LPG station.

The input consists of several datasets. Each dataset has the following format:

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)

The first line contains three integers $N$, $M$, and $cap$, where $N$ ($1 \le N \le 3000$) is the number of roads, $M$ ($1 \le M \le 300$) is the number of LPG stations, and $cap$ ($1 \le cap \le 200$) is the tank capacity in liters. The next line contains the name of the starting city $src$ and the destination city $dest$; the destination is always different from the start. Each of the next $N$ lines describes a road: road $i$ ($1 \le i \le N$) connects two distinct cities $c_{i,1}$ and $c_{i,2}$ with an integer distance $d_i$ ($0 < d_i \le 2000$) in kilometers, and it can be traveled in either direction. No two distinct roads connect the same pair of cities, and columns are separated by a single space. The following $M$ lines list the names of the cities that have an LPG station; every such city has at least one road.

A city name has at most 15 characters, using only English letters ('A'-'Z' and 'a'-'z', case sensitive).

A line containing three zeros terminates the input.

For each dataset, print a single line with the length in kilometers of the shortest possible journey from the starting city to the destination. If Nakamura cannot reach the destination, print $-1$. Do not print any other characters.

The real tank capacity is usually slightly larger than the specification, so he can reach a city even when the remaining gas becomes exactly zero. He can also always refill at the destination, so the return trip does not matter.