Problem A
Bring Your Own Horse

One of the essential activities of a knight is to compete in tournaments. Frequently, groups of knights gather around the country to compare their skills. On such a typical contest day, everyone has five hours to do ten disciplines, such as sword fighting, bow and arrow, and various forms of horseback riding. Needless to say, you have to bring your own horse.

This is not as easy as it seems. It often takes a knight several days to go from the castle where he lives to the place where a tournament is held. But horses sometimes are very, very stubborn. After having covered a certain distance on a single day, they sometimes simply stop and refuse to go any further. Luckily, they start anew on the next day. To make sure that the horse does not refuse service before the scheduled day trip is completed, a knight wants to choose an itinerary on which the longest day trip is as short as possible. Hence, a trip that takes many days with short distances is preferable over a shorter route that has the risk of a refusing horse.

Write a program which answers queries from knights spread all over the country about the best way to go from their castles to a tournament site. Given a description of the relevant places (i.e. castles, locations of tournaments, and hostels for overnight stays), the program should tell them the largest distance they have to cover on a single day so that this distance is minimal among all possible itineraries.

The places are designated by consecutive integers from 1 to $N$, while a road is represented by three integers, namely its place of origin, its destination, and its length. Every road can be used in both directions, and there is at least one route (i.e. a sequence of roads) between any two places. The knights stick to the given roads while travelling and spend their nights only at one of the $N$ places.

Input
The first line contains the total number of test cases that follow.

Each test case begins with a line that first holds the number $N$ of places ( $1 \le N \le 3000$ ) followed by the number $R$ of roads ( $1 \le R \le 100000$ ). Then there are $R$ lines with three integers each ($a$ , $b$ , and $l$ ), each of which defines a road connecting the places $a$ and $b$ ( $1 \le a, b \le N$ ) with length $l$ ( $1 \le l \le 1000000$ ).

Thereafter, each test case continues with the number $Q$ of queries on a line by itself ( $1 \le Q \le 1000$ ). Each of the next $Q$ lines holds two integers $k$ and $t$ , indicating a query by a knight who lives at place $k$ and needs to go to a tournament at place $t$ ( $1 \le k, t \le N$ , $k \neq t$ ).

Output
For each test case output a line containing the word ``Case'', a single space, and its serial number (starting with $1$ for the first test case). Then, print one line for each query in this test case, containing the smallest maximal day trip distance as described above. Print a blank line after each test case.

Sample Input

2
4 4
1 2 100
2 3 100
3 4 100
4 1 200
1
1 4
6 9
2 4 5
5 1 7
3 6 6
3 1 4
2 3 2
1 2 1
6 5 42
4 5 3
4 6 5
4
1 3
3 4
5 4
6 1
 

Sample Output

Case 1
100

Case 2
2
5
3
5