Vice City

"Tommy, there will be a programming contest here in Vice City. One of the coaches has stolen a copy of the problem set. The chief judge wants it back. Take out the coach at his hotel and bring the problems back. The address is taped under the phone. Do it now!"

Not a tough job for you, Tommy Vercetti! After grabbing the mission at the pay phone, you must reach the coach at the WK Charriot Hotel before he leaves — and you must get there as fast as you possibly can. Unfortunately, the vehicle you start with may not be fast enough. Luckily, there are fixed locations around Vice City where a particular vehicle is always parked — for example, Diaz's Mansion, where an Infernus is waiting. So you may swap vehicles several times on the way to the hotel. Each time you change vehicles it costs you one minute.

You start at PayPhone already driving the vehicle parked there (this starting vehicle costs no change time), and your goal is WKCharriot. You are given the names of the locations in the city and the distances between connected pairs. At each location a specific vehicle is available whenever you arrive there. Knowing the top speed of every vehicle, find the minimum time needed to reach the hotel. For simplicity, assume you always drive at the top speed of your current vehicle, so travelling a road of length $d$ kilometers at speed $s$ km/h takes $60 \cdot d / s$ minutes.

The first line contains a single integer $t$ ($1 \le t \le 20$), the number of test cases. Each test case has three parts, and consecutive parts are separated by exactly one blank line.

The first part consists of $m$ lines ($1 \le m \le 100$), each of the form vehicle speed, where vehicle is the unique name of a vehicle and speed is a positive integer giving its top speed in km/h.

The second part consists of $n$ lines ($2 \le n \le 500$), each of the form location vehicle, where location is the unique name of a location and vehicle is the vehicle parked there. The list of locations always includes the starting location PayPhone and the destination WKCharriot.

The third part lists the roads, each of the form loc1 loc2 distance, meaning there is a two-way road of the given positive integer length (in kilometers) between loc1 and loc2. This part is terminated by a line containing a single asterisk (*).

All vehicle and location names are strings of at most 100 letters and digits with no spaces, and are case sensitive. Items on a line are separated by one or more spaces, and lines may have arbitrary leading or trailing blanks except for the empty separator lines.

For each test case, print a single line with the minimum time, in minutes, to travel from PayPhone to WKCharriot, or the word UNREACHABLE if the destination cannot be reached from the start.

Print the time with exactly three digits after the decimal point. Any digits beyond the third are truncated (ignored, not rounded), and if fewer than three digits are present they are padded with zeros.