바이스 시티

"토미, 여기 바이스 시티에서 프로그래밍 대회가 열릴 거야. 코치 한 명이 문제 세트 사본을 훔쳐 갔어. 심사위원장이 그걸 되찾고 싶어 해. 그 코치가 묵는 호텔로 가서 처리하고 문제를 되찾아 와. 주소는 전화기 밑에 붙여 뒀어. 지금 당장 움직여!"

토미 버세티, 너에게는 어려운 일이 아니지! 공중전화에서 임무를 받은 뒤, 코치가 떠나기 전에 WK 채리엇 호텔에 도착해야 한다. 그것도 최대한 빨리. 안타깝게도 처음 타고 있는 차량은 충분히 빠르지 않을 수 있다. 다행히 바이스 시티에는 특정 차량이 항상 세워져 있는 고정된 장소들이 있다. 예를 들어 디아즈의 저택에는 인페르누스가 있다. 그래서 호텔로 가는 길에 차량을 여러 번 바꿔 탈 수 있다. 단, 차량을 바꿀 때마다 1분이 걸린다.

출발지는 PayPhone이며, 처음부터 그곳에 세워진 차량을 몰고 시작한다(이 최초 차량에는 교체 시간이 들지 않는다). 목적지는 WKCharriot이다. 도시의 장소 이름들과 연결된 장소 쌍 사이의 거리가 주어진다. 각 장소에 도착하면 언제든 그 장소에 있는 특정 차량을 탈 수 있다. 모든 차량의 최고 속도를 알고 있을 때, 호텔에 도착하기까지 걸리는 최소 시간을 구하여라. 계산을 단순하게 하기 위해 항상 현재 차량의 최고 속도로 달린다고 가정한다. 즉, 길이가 $d$ 킬로미터인 도로를 속도 $s$ km/h로 지나는 데 $60 \cdot d / s$ 분이 걸린다.

첫째 줄에 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \le t \le 20$)가 주어진다. 각 테스트 케이스는 세 부분으로 이루어지며, 연속한 두 부분은 정확히 한 개의 빈 줄로 구분된다.

첫 번째 부분은 $m$개의 줄($1 \le m \le 100$)로 이루어지고, 각 줄은 vehicle speed 형식이다. vehicle은 차량의 고유한 이름이고 speed는 그 차량의 최고 속도를 나타내는 양의 정수(km/h)이다.

두 번째 부분은 $n$개의 줄($2 \le n \le 500$)로 이루어지고, 각 줄은 location vehicle 형식이다. location은 장소의 고유한 이름이고 vehicle은 그 장소에 있는 차량이다. 장소 목록에는 항상 출발지 PayPhone과 목적지 WKCharriot이 포함된다.

세 번째 부분은 도로들을 나타내며, 각 줄은 loc1 loc2 distance 형식이다. 이는 loc1과 loc2 사이에 길이가 주어진 양의 정수(킬로미터)인 양방향 도로가 있음을 뜻한다. 이 부분은 별표 하나(*)만 있는 줄로 끝난다.

모든 차량 이름과 장소 이름은 공백이 없는 100자 이하의 영문자와 숫자로 이루어진 문자열이며, 대소문자를 구분한다. 한 줄 안의 항목들은 하나 이상의 공백으로 구분되고, 빈 구분 줄을 제외한 각 줄에는 앞뒤로 임의의 공백이 있을 수 있다.

각 테스트 케이스마다 한 줄에, PayPhone에서 WKCharriot까지 이동하는 데 걸리는 최소 시간(분)을 출력한다. 목적지에 도달할 수 없으면 UNREACHABLE을 출력한다.

시간은 소수점 아래 정확히 세 자리까지 출력한다. 세 번째 자리보다 아래의 숫자는 반올림하지 않고 버리며(무시하며), 소수점 아래 자릿수가 세 자리보다 적으면 0으로 채운다.