URI Online Judge | 2086

Bike Land

By Gabriel Duarte, UNIFESO BR Brazil

Timelimit: 1

As you all know, the mayoral elections are coming. This year our city has excellent candidates, all with incredible government proposals.

One candidate intends to implement a revolutionary transport system, where the streets will be removed and exchanged for bike lanes. This idea seems to be the solution to all the problems that our city is facing. But there is a flaw: dehydration when we walk long time in a bike.

To solve this problem, the applicant intends to provide chilled water for the entire population. His idea is to place distribution points in all intersections of the bike lane. But as water is a resource that is running out, the amount that it will provide will be fixed, regardless of the distance traveled by the individual.

Intending to validate your idea, the candidate hired you to help. Your task is simple: will be provided the city map with all the intersections and the distances between them. Then you must answer several candidate queries, where it will provide two intersections, A and B, and your program will show what the greatest distance to be traveled by a person without water between A and B. With this information the candidate able see if the amount that it intends to provide will suffice. Do not forget that the candidate intends to reduce this distance, then your program should inform the greatest distance in the best way.

As the streets of our city are very wide, all bike lanes will be two-way.

Input

The entrance has several test cases. Each test case begins with two integers N (1 ≤ N ≤ 100) and M (1 ≤ M ≤ 4950), respectively indicating the number of intersections in the city map and how many bike lanes will be created. In the next M lines will be provided three integers U, V (1 ≤ U, V N) and W (0 ≤ W ≤ 2000), indicating that there is a bike lane between the U and V intersect wiht a distance W. The next line will have an integer Q (1 ≤ Q ≤ 50), which represents the number of queries that the candidate wants to do. Here Q lines with two integers A and B (1 ≤ A, BN) indicating the pair of intersections for which the query must be made. The entry ends when N = M = 0 and should not be processed.

Output

Input Sample Output Sample

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
 

4
3
6
1