beecrowd | 1454

The Country of Bicycles

VIII Maratona de Programação IME-USP Brazil
Timelimit: 3

As you may already know, the bicycle is one of the most popular means of transportation in China. Almost all Chinese have one, and they use it for work, recreation, and other activities.

After many years riding, Mr. Lee no longer have the same willingness to face the various ascents of the city where he lives. And the city where Mr. Lee lives is extremely mountainous. For sentimental reasons, he did not want to move to a flat city. He decided then to try to avoid high altitudes in his paths even if he had to ride a little more.

Mr. Lee obtained with the Chinese topographical service, a collection of maps of his town, in every street in these maps it is possible to see the highest altitude found when traveling over it. All he needs to do now is to determine routes that minimize the time traveled between pairs (source, destination).

Knowing that you plan to visit the city in which he lives next year, Mr. Lee asked for your help. In a first step, he wants you to implement a program that receives topographic maps of the city and a collection of pairs (source, destination). For each pair, your program should print the maximum height found on a route between source and destination. Remember that routes should minimize such heights. The routes themselves, will be determined in a second step (when you come to China to visit him).

Since the bicycle is used for transportation, you can consider that all the streets are two-way. Do not delay, because Mr. Lee is counting on you. :-)

Input

Your program must be prepared to work with several maps, called instances. Each instance has the following structure.

In the first row are given two integers n (0 ≤ n ≤ 100) in (0 ≤ m ≤ 4950) which represent, respectively, the numbers of intersections and streets. For clarity, the intersections are numbered from 1 to n, inclusive; every street begins and ends at an intersection, and there are no intersections off the ends of a street.

In the next m lines it is provided three integers i and j (1 ≤ i, jn) indicating the existence of a street between intersections i and j and h representing the highest altitude found when the street is traveled over. These integers are separated by blank spaces.

On the next line, it is given an integer k (1 ≤ k ≤ 50) that represents the number of pairs (source, destination) that will be specified in the next k lines. Each pair consists of two integers i and j as described above. That is, the source and the destination are intersections of two streets, and are also separated by whitespace.

Values n = m = 0 indicates the end of instances and should not be processed.

Output

For each instance solved, you should print a handle Instancia h where h is an integer, sequentially increasing from 1. In the next k lines, you must print the greatest heights found on routes between the k pairs (source, destination) provided, one value per line, in the order they appeared in the input.

A blank line must be printed after each instance.

Sample Input Sample Output

12 17
1 4 4
4 7 6
7 10 6
2 5 4
5 8 5
8 11 2
3 6 5
6 9 3
9 12 1
1 2 1
2 3 9
4 5 3
5 6 7
7 8 7
8 9 2
10 11 1
11 12 2
4
1 5
6 8
6 7
11 10
0 0

Instancia 1
4
3
6
1