Roads Scholar

The Hines Sign company supplies roadside mile-marker signs for a state highway system. For one class of signs, each sign lists nearby cities together with the distance a traveller must go to reach each one.

A sign is placed at a fixed point on a road and faces the direction of travel along that road. Let $A$ be the intersection immediately behind the sign — the one the traveller has just left. A city $X$ is listed on the sign exactly when the shortest path from $A$ to $X$ begins by travelling along the very road the sign sits on. You may assume the shortest path between any two intersections is unique.

The distance printed for a listed city $X$ is the length of the shortest route from the sign itself to $X$; that is, the shortest distance from $A$ to $X$ minus the distance from $A$ to the sign.

The first line contains a single integer $T$: the number of test cases. A blank line precedes each test case.

Each test case describes one highway system and then a list of sign placements.

The first line of a test case has three integers $n$, $m$, $k$: $n$ is the number of intersections (numbered $0, 1, \dots, n - 1$), $m$ is the number of roads, and $k$ is the number of intersections that are also cities.

The next $m$ lines each contain i1 i2 d: a two-way road between intersections i1 and i2 whose length is d.

The next $k$ lines each contain i name: intersection i is a city called name.

The next line contains a single integer $s$: the number of signs. Each of the following $s$ lines contains i1 i2 d: a sign placed on the road from i1 toward i2, at distance d from i1 (where $0 < d$ and d is strictly less than the length of that road).

Every name has length at most $18$, $5 \le n \le 30$, and every distance is positive and given to the nearest hundredth of a mile.

For each test case, print the result for every sign in the order the signs are given. For a single sign, print one line per listed city:

name distance

Here name is the city name, followed by one space, followed by distance — the distance from the sign to that city rounded to the nearest mile (a value ending in exactly $.50$ rounds up; for example $7.50$ becomes $8$).

Within one sign, sort the lines by rounded distance in ascending order, breaking ties by city name in alphabetical order. Separate consecutive signs with a blank line, and separate the outputs of consecutive test cases with a blank line. Every sign lists at least one city.