So it's Christmas! And Santa Claus needs to perform a series of deliveries of gifts in different locations around the world.

For those who do not know, the reindeers are sick and he will need to use the gas-powered thunder to deliver the presents.

A curious fact is that the roads between cities are perfectly straight and there is a gas station in each city. Santa Claus is a very smart guy and, to avoid problems, he fills the tank with a specific value X

is the value of the largest road between the cities that Santa is traveling, so he knows that he will never run out of gas between the two cities and the gifts will not be stolen. In addition, it always selects the path where the largest road is as minimum as possible.

Can you help the Santa Claus determine what X value of gas he should use?

Input

The first line is composed of two integers N (1≤N≤1×105) and M (N−1≤M≤min(2×105,(N×(N−1))/2))is the number of cities and the number of roads. Next come M lines with three integers u, v, w (u≠v)(0≤u,v<N)(1≤w≤1×106), that there is a road connecting it with weight (you can use the road in any direction). After M lines, has an integer Q (1≤Q≤1×105)  is the number of queries that Santa Claus will perform. Each of Q lines is composed of two integers  x and y (0≤x,y,<N) corresponds to the query: how much X  gasoline that Santa Claus will need to supply in every city between the cities  x and y.

Output

Print Q lines each with an integer X is the answer of the dilemma what Santa Claus is passed.

Example

Input:
 7 11
 0 1 15
 0 2 53
 1 2 40
 1 3 46
 2 4 31
 2 5 29
 3 4 3
 4 5 29
 3 6 11
 4 6 8
 5 6 40
 7
 0 1
 0 3
 0 6
 2 4
 4 6
 5 1
 1 1
Output:
15
 40
 40
 29
 8
 40
 0