Server Time: Wed Oct 16, 2019 5:17 am
Welcome ( logout
1101 - A Secret Mission
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 64 MB

All of you have heard about Evil Jack Diablo, the one who had stolen the whole problem set from the Good Judges last time. Once again he is making evil plans, but he does not know that Alice is on a secret mission. There will be several pairs of City of Evils on the way of Alice's mission.

There will be N evil cities (numbered by 1, 2, ..., N) connected by M bidirectional roads. There will be evil guards patrolling the roads. Since they are not much intelligent, the danger of travelling in each road is not the same. Alice is going to travel from city s to city t. You can safely assume that it's possible to travel from any city to another. John the legend programmer has estimated the danger of each road but since he is busy arranging contests, Alice is depending on you now. Danger of a path from city s to city t is defined as the maximum danger of any road on this path. As you are one of the most talented programmers, you will love to help Alice by finding the least dangerous paths to prevent Evil Jack from doing harms to the Judges.

Input

Input starts with an integer T (≤ 3), denoting the number of test cases.

Each case contains two integers N, M (2 ≤ N ≤ 50000, 1 ≤ M ≤ 105) denoting the number of cities and roads. Each of the next M lines contains three integers: xi, yi, di (1 ≤ xi, yi ≤ N, xi ≠ yi, 1 ≤ di ≤ 104) - the cities connected by the ith road and its degree of danger. Next line contains an integer q (1 ≤ q ≤ 50000). Each of the next q lines contains two integers: si and ti (1 ≤ si, ti ≤ N, si ≠ ti).

Output

For each test case, print the case number first. Then for each query si ti, print the least dangerous path in a line.

Sample Input

Output for Sample Input

2

4 5

1 2 10

1 3 20

1 4 100

2 4 30

3 4 10

2

1 4

4 1

2 1

1 2 100

1

1 2

Case 1:

20

20

Case 2:

100

Notes

Dataset is huge, use faster i/o methods.


Problem Setter: Syed Irfan Nabil
Special Thanks: Jane Alam Jan (Solution, Dataset)
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan