All of you have heard about the 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 to 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 traveling 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 one 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. The 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 harm to the Judges.

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 ≤ 10⁵) denoting the number of cities and roads. Each of the next M lines contains three integers: x_i, y_i, d_i (1 ≤ x_i, y_i ≤ N, x_i ≠ y_i, 1 ≤ d_i ≤ 10⁴) - the cities connected by the i^th road and its degree of danger. Next line contains an integer q (1 ≤ q ≤ 50000). Each of the next q lines contains two integers: s_i and t_i (1 ≤ s_i, t_i ≤ N, s_i ≠ t_i).

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

Dataset is huge, use faster I/O methods.