형편없는 우편물 전달

Masa가 사는 지역의 우편 시스템은 조금 특이하다. 이 지역에서는 각 우편국에 1부터 시작하는 연속된 서로 다른 번호가 붙어 있고, 어떤 우편국에 도착한 우편물은 그 우편국에서 여러 우편국을 거쳐 목적지 우편국으로 전달된다. 우편물의 "전달"은 특정한 우편국 사이에서만 이루어진다. 다만 전달이 이루어지는 우편국 사이에서는 전달이 양방향으로 이루어진다.

어떤 우편국에서 목적지까지 우편물을 전달하는 경로가 여러 개 존재하면, 목적지까지의 거리가 최단이 되는 경로를 사용한다. 따라서 전달지는 그 최단 경로에서 다음 우편국이 된다. 총거리가 최단이 되는 경로가 여러 개 존재하면, 직접적인 전달지가 되는 우편국의 번호가 더 작은 쪽으로 전달한다.

그런데 이 지역은 심각한 노동력 부족에 시달리고 있어, 우편국 사이의 전달을 담당하는 전달원이 각 우편국에 한 명씩밖에 없다. 그들이 열심히 왕복하고 있는 것이다. 당연히 어떤 우편국에 우편물이 도착한 시점에 그 우편국에 소속된 전달원이 나가 있으면, 그 우편국에서의 전달은 일시적으로 멈춘다.

그들은 자신이 소속된 우편국에 있을 때, 그 우편국에서 전달되지 않은 우편물이 존재하면 즉시 출발하고, 전달지에 도착한 뒤에는 즉시 돌아온다. 그가 전달지 우편국에서 돌아올 때, 자기 우편국으로 전달되는 우편물이 그 우편국에 있더라도 그것을 운반해 오지는 않는다(그 우편물의 전달은 그 우편국의 전달원이 할 일이다).

전달할 때 여러 우편물이 쌓여 있으면, 그 우편국에 가장 일찍 도착한 우편물부터 전달한다. 여기서 같은 시각에 도착한 우편물이 여러 개 있으면, 직접적인 전달지가 되는 우편국의 번호가 더 작은 쪽부터 전달한다. 같은 전달지로 가는 우편물이 있으면 그것도 함께 전달한다. 또한 전달원의 출발 시각과 같은 시각에 같은 우편국으로 전달되어야 할 우편물이 도착하면, 그것도 함께 전달된다. 그리고 그들은 모두 거리 1을 이동하는 데 시간 1이 걸린다.

당신에게는 우편국 사이의 전달에 관한 정보와 각 우편국에 우편물이 도착한 시각의 목록이 주어진다. 이때 우편물의 움직임을 시뮬레이션하여, 각 우편물이 목적지 우편국에 도착한 시각을 보고하라. 문제의 시뮬레이션 중에 필요한 시각은 모두 0 이상 231 미만의 범위에 들어간다고 가정해도 좋다.

입력은 여러 데이터 세트로 이루어지며, 입력의 끝은 0 0만 적힌 한 줄로 나타난다. 각 데이터 세트의 형식은 다음과 같다.

데이터 세트의 첫 줄에는 정수 n (2 ≤ n ≤ 32)과 m (1 ≤ m ≤ 496)이 1개의 공백으로 구분되어 순서대로 주어진다. n은 우편국의 총수를, m은 우편국 사이의 직접 전달 경로의 수를 나타낸다. 어떤 두 우편국 사이에 직접 전달 경로가 2개 이상 존재하지는 않는다.

이어지는 m 줄에는 우편국 사이의 직접 전달 경로 정보를 적은 3개의 정수가 주어진다. 첫 번째와 두 번째가 전달 경로 양 끝 우편국의 번호(1 이상 n 이하)이고, 마지막 정수가 그 두 우편국 사이의 거리를 나타낸다. 거리는 1 이상 10000 미만이다.

다음 줄에는 처리할 우편물의 수를 나타내는 정수 l (1 ≤ l ≤ 1000)이 주어지고, 이어지는 l 줄에 각 우편물의 상세 정보가 주어진다. 각 줄의 앞에는 3개의 정수가 적혀 있다. 이들은 순서대로 발송원 우편국의 번호, 목적지 우편국의 번호, 발송원 우편국에 도착한 시각이다. 줄의 끝에는 우편물의 라벨을 나타내는 문자열이 적힌다. 이 라벨은 길이가 1 이상 50 이하이고, 알파벳, 숫자, 하이픈('-'), 밑줄('_')로만 이루어진다. 각 우편물의 정보는 발송원 우편국에 도착한 시각 순으로 적혀 있다. 같은 시각일 때는 순서가 특별히 정해져 있지 않다. 또한 같은 라벨의 우편물이나, 발송원과 목적지가 같은 우편물, 또는 배달 경로가 존재하지 않는 우편물은 존재하지 않는다.

입력 줄에서 각 숫자나 문자열의 구분은 모두 1개의 공백이다.

각 데이터 세트에 대해 l줄을 출력한다. 각 출력은 다음 형식을 따른다.

각 우편물에 대해, 그 우편물이 도착한 시각을 한 줄에 출력한다. 그 줄에는 먼저 우편물의 라벨을 출력하고, 다음에 1개의 공백을 넣고, 마지막으로 우편물이 목적지 우편국에 도착한 시각을 출력한다. 이들은 도착 시각 순으로 출력한다. 같은 시각에 도착한 우편물이 여러 개 있으면, 그 라벨의 ASCII 코드 오름차순으로 출력한다.

각 데이터 세트에 대응하는 출력 사이에 빈 줄을 1개 삽입한다.