Poor Mail Forwarding

The postal system in the area where Masa lives has changed a bit. In this area, each post office is numbered consecutively from 1 to a different number, and mail delivered to a post office is intended from that post office via several post offices. Delivered to the post office. Mail "forwarding" is only done between specific post offices. However, the transfer is bidirectional between the post offices where the transfer is performed.

If there are multiple routes for forwarding mail from a post office to the destination, use the route that minimizes the distance to the destination. Therefore, the forwarding destination will be the next post office on such a shortest path. If there are multiple routes with the shortest total distance, the postal office number that is the direct transfer destination is transferred to the younger one.

By the way, the region is suffering from a serious labor shortage, and each post office has only one transfer person to transfer between post offices. They are doing their best to go back and forth. Of course, if the forwarding agent belonging to a post office has paid the mail when the mail arrives at that post office, the forwarding from that post office will be temporarily stopped.

When they are at their post office, they depart immediately if there is mail that has not been forwarded from that post office, and return immediately after delivering it to the forwarding destination. When he returns from the destination post office, he will not carry the mail that will be forwarded to his post office, even if it is at that post office (the mail will be forwarded to that mail). It is the job of the post office transferman).

If multiple mail items are collected at the time of forwarding, the mail that was delivered to the post office earliest is transferred first. Here, if there are multiple mail items that arrived at the same time, the mail is forwarded from the one with the youngest post office number that is the direct forwarding destination. If there is mail that has the same forwarding destination, it will also be forwarded together. Also, if the mail that should be forwarded to the same post office arrives at the same time as the forwarding agent's departure time, it will also be forwarded. It should be noted that they all take 1 time to travel a distance of 1.

You will be given information about the transfer between post offices and a list of the times when the mail arrived at each post office. At this time, simulate the movement of the mail and report the time when each mail arrived at the destination post office. It can be assumed that all the times required during the simulation of the problem are in the range 0 or more and less than 231.

Input

The input consists of multiple datasets, and the end of the input is represented by a single line with only 0 0. The format of each dataset is as follows.

The first line of the dataset is given the integers n (2 <= n <= 32) and m (1 <= m <= 496), separated by a single character space. n represents the total number of post offices and m represents the number of direct forwarding routes between post offices. There can never be more than one direct forwarding route between two post offices.

On the next m line, three integers containing information on the direct transfer route between stations are written. The first and second are the postal numbers (1 or more and n or less) at both ends of the transfer route, and the last integer represents the distance between the two stations. The distance is greater than or equal to 1 and less than 10000.

The next line contains the integer l (1 <= l <= 1000), which represents the number of mail items to process, followed by the l line, which contains the details of each piece of mail. Three integers are written at the beginning of each line. These are, in order, the sender's postal office number, the destination postal office number, and the time of arrival at the sender's postal office. At the end of the line, a string representing the label of the mail is written. This label must be between 1 and 50 characters in length and consists only of letters, numbers, hyphens ('-'), and underscores ('_'). Information on each of these mail items is written in chronological order of arrival at the post office of the sender. At the same time, the order is not specified. In addition, there is no mail with the same label, mail with the same origin and destination, or mail without a delivery route.

Each number or string in the input line is separated by a single character space.

Output

Output l lines for each dataset. Each output follows the format below.

For each mail, the time when the mail arrived is output on one line. On that line, first print the label of the mail, then with a one-character space, and finally print the time when the mail arrived at the destination post office. These are output in order of arrival time. If there are multiple mails arriving at the same time, the ASCII code of the label is output in ascending order.

A blank line is inserted between the outputs corresponding to each dataset.

Example

Input

4 5 1 2 10 1 3 15 2 3 5 2 4 3 3 4 10 2 1 4 10 LoveLetter 2 3 20 Greetings 3 3 1 2 1 2 3 1 3 1 1 3 1 2 1 BusinessMailC 2 3 1 BusinessMailB 3 1 1 BusinessMailA 0 0

Output

Greetings 25 LoveLetter 33

BusinessMailA 2 BusinessMailB 2 BusinessMailC 2

inputFormat

Input

The input consists of multiple datasets, and the end of the input is represented by a single line with only 0 0. The format of each dataset is as follows.

The first line of the dataset is given the integers n (2 <= n <= 32) and m (1 <= m <= 496), separated by a single character space. n represents the total number of post offices and m represents the number of direct forwarding routes between post offices. There can never be more than one direct forwarding route between two post offices.

On the next m line, three integers containing information on the direct transfer route between stations are written. The first and second are the postal numbers (1 or more and n or less) at both ends of the transfer route, and the last integer represents the distance between the two stations. The distance is greater than or equal to 1 and less than 10000.

The next line contains the integer l (1 <= l <= 1000), which represents the number of mail items to process, followed by the l line, which contains the details of each piece of mail. Three integers are written at the beginning of each line. These are, in order, the sender's postal office number, the destination postal office number, and the time of arrival at the sender's postal office. At the end of the line, a string representing the label of the mail is written. This label must be between 1 and 50 characters in length and consists only of letters, numbers, hyphens ('-'), and underscores ('_'). Information on each of these mail items is written in chronological order of arrival at the post office of the sender. At the same time, the order is not specified. In addition, there is no mail with the same label, mail with the same origin and destination, or mail without a delivery route.

Each number or string in the input line is separated by a single character space.

outputFormat

Output

Output l lines for each dataset. Each output follows the format below.

For each mail, the time when the mail arrived is output on one line. On that line, first print the label of the mail, then with a one-character space, and finally print the time when the mail arrived at the destination post office. These are output in order of arrival time. If there are multiple mails arriving at the same time, the ASCII code of the label is output in ascending order.

A blank line is inserted between the outputs corresponding to each dataset.

Example

Input

4 5 1 2 10 1 3 15 2 3 5 2 4 3 3 4 10 2 1 4 10 LoveLetter 2 3 20 Greetings 3 3 1 2 1 2 3 1 3 1 1 3 1 2 1 BusinessMailC 2 3 1 BusinessMailB 3 1 1 BusinessMailA 0 0

Output

Greetings 25 LoveLetter 33

BusinessMailA 2 BusinessMailB 2 BusinessMailC 2

样例

4 5
1 2 10
1 3 15
2 3 5
2 4 3
3 4 10
2
1 4 10 LoveLetter
2 3 20 Greetings
3 3
1 2 1
2 3 1
3 1 1
3
1 2 1 BusinessMailC
2 3 1 BusinessMailB
3 1 1 BusinessMailA
0 0

Greetings 25
LoveLetter 33
BusinessMailA 2
BusinessMailB 2
BusinessMailC 2

</p>