Roads Scholar

하인스 사인(Hines Sign) 회사는 주(州) 고속도로망에 세울 도로 표지판을 공급한다. 그중 한 종류의 표지판은 근처 도시들의 이름과, 그 도시까지 가려면 얼마나 더 가야 하는지의 거리를 함께 표시한다.

표지판은 어떤 도로 위의 한 지점에 세워지며, 그 도로를 따라가는 진행 방향을 향한다. 표지판 바로 뒤쪽, 즉 운전자가 방금 지나온 교차로를 $A$라고 하자. 도시 $X$는 $A$에서 $X$로 가는 최단 경로가 바로 그 표지판이 세워진 도로를 따라 출발할 때에만 표지판에 표시된다. 임의의 두 교차로 사이의 최단 경로는 유일하다고 가정해도 된다.

표시되는 도시 $X$에 대해 적히는 거리는 표지판 자신에서 $X$까지의 최단 거리이다. 즉, $A$에서 $X$까지의 최단 거리에서 $A$부터 표지판까지의 거리를 뺀 값이다.

첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나씩 놓인다.

각 테스트 케이스는 하나의 고속도로망과, 그에 이어지는 표지판 위치 목록으로 이루어진다.

테스트 케이스의 첫 줄에는 세 정수 $n$, $m$, $k$가 주어진다. $n$은 교차로의 수(번호는 $0, 1, \dots, n - 1$), $m$은 도로의 수, $k$는 교차로 중 도시이기도 한 곳의 수이다.

이어지는 $m$개의 줄에는 각각 i1 i2 d가 주어지며, 이는 교차로 i1과 i2를 잇는 길이 d의 양방향 도로를 뜻한다.

그다음 $k$개의 줄에는 각각 i name이 주어지며, 이는 교차로 i가 name이라는 이름의 도시임을 뜻한다.

그다음 줄에는 표지판의 수를 나타내는 정수 $s$가 주어진다. 이어지는 $s$개의 줄에는 각각 i1 i2 d가 주어지며, 이는 i1에서 i2로 향하는 도로 위, i1로부터 거리 d인 지점에 표지판을 세운다는 뜻이다(여기서 $0 < d$이며, d는 그 도로의 길이보다 반드시 작다).

모든 name의 길이는 최대 $18$이고, $5 \le n \le 30$이며, 모든 거리는 양수이고 $0.01$ 마일 단위로 주어진다.

각 테스트 케이스에 대해, 입력에 주어진 순서대로 모든 표지판의 결과를 출력한다. 하나의 표지판에 대해서는 표시되는 도시마다 한 줄씩 출력한다.

name distance

여기서 name은 도시 이름이고, 그 뒤에 공백 한 칸, 그다음에 distance가 온다. distance는 표지판에서 그 도시까지의 거리를 가장 가까운 마일로 반올림한 값이다(정확히 $.50$으로 끝나면 올림한다. 예를 들어 $7.50$은 $8$이 된다).

한 표지판 안에서는 반올림한 거리의 오름차순으로 줄을 정렬하고, 거리가 같으면 도시 이름의 알파벳순으로 정렬한다. 연속한 두 표지판의 출력 사이에는 빈 줄을 하나 넣고, 연속한 두 테스트 케이스의 출력 사이에도 빈 줄을 하나 넣는다. 모든 표지판에는 적어도 하나의 도시가 표시된다.