Einbahnstrasse

Einbahnstraße (German for a one-way street) is a street on which vehicles may move in only one direction. One reason for one-way streets is to make traffic flow more smoothly through crowded areas. This is useful in city centers, especially in old cities such as Cairo and Damascus. Careful planning guarantees that you can reach any location starting from any point. Even so, drivers must plan their route carefully to avoid lengthening their trip because of one-way streets. Experienced drivers know that there are multiple paths between any two locations. On top of that, there may be several roads between the same two locations. Knowing the shortest route between any two locations is a must, and it matters even more when driving vehicles that are hard to maneuver (garbage trucks, tow trucks, etc.).

You have just started a new job at a car-towing company. The company keeps a number of tow trucks parked at its garage. A tow truck lifts the front or back wheels of a broken-down car and pulls it straight back to the company's garage. You receive calls from all over the city about broken-down cars that need towing, and the cars must be towed in the same order the calls arrive. Your job is to advise the tow-truck drivers on the shortest way to collect every broken-down car back at the garage. At the end of the day, you must report to management the total distance traveled by the trucks.

Your program is tested on one or more test cases. The first line of each test case gives three numbers $N$, $C$, and $R$, separated by one or more spaces. The city has $N$ locations with distinct names, including the company's garage. $C$ is the number of broken-down cars and $R$ is the number of roads in the city. The limits are $0 < N < 100$, $0 \le C < 1000$, and $R < 10000$. The second line consists of $C + 1$ words: the first is the location of the company's garage, and the rest are the locations of the broken-down cars. A location name is a word of at most 10 letters, and letter case is significant. After the second line come exactly $R$ lines, each describing a road. A road is written in one of these three formats:

A --v-> B
A <-v-- B
A <-v-> B

$A$ and $B$ are the names of two different locations, and $v$ is a positive integer (at most 1000) giving the length of the road. The first format is a one-way street from $A$ to $B$, the second is a one-way street from $B$ to $A$, and the third is a two-way street between them. $A$, the arrow, and $B$ are separated by one or more spaces. The end of the input is a line with three zeros (for $N$, $C$, and $R$).

For each test case, print the total distance traveled in the following format:

k. V

Here $k$ is the test-case number (starting at 1), the dot is followed by a single space, and $V$ is the result.

Each broken-down car is towed on its own: the tow truck leaves the garage, drives to the car's location, and returns to the garage. The total distance is therefore the sum, over all broken-down cars, of the shortest distance from the garage to the car plus the shortest distance from the car back to the garage. When several roads connect the same two locations, use the shortest one.