Maximum Cargo Weight Transport

A country has n cities numbered from 1 to n and m bidirectional roads. Each road has a weight limit, which restricts the maximum weight that may cross it. There are q queries, each corresponding to a truck journey from a source city to a destination city. For each query, determine the maximum cargo weight that can be transported along some route without exceeding any road's weight limit.

The problem can be reformulated as follows. Consider a path from city s to city t in the graph. The cargo weight that can be transported along that path is limited by the smallest weight limit among all roads on the path. In other words, if the path uses roads with limits w₁, w₂, ... , w_k, then the maximum cargo weight the truck can carry along that route is
\( \min\{w_1, w_2, \dots, w_k\} \).
Your task is to choose a route such that this value is maximized, and output that maximum cargo weight for each query. If there is no valid route between the specified cities, output 0.

Note: All formulas are in LaTeX format.

inputFormat

The first line contains two integers n and m — the number of cities and the number of roads.

The next m lines each contain three integers u, v, and w where there is a bidirectional road between cities u and v with weight limit w (\(w > 0\)).

The next line contains a single integer q — the number of queries.

Each of the following q lines contains two integers s and t representing the source and destination cities for a truck.

outputFormat

For each query, output a single integer — the maximum cargo weight that can be transported from city s to city t without exceeding the roads' weight limits. If no route exists, output 0.

sample

4 5
1 2 10
2 3 5
3 4 7
1 3 8
2 4 6
3
1 4
2 3
1 3

7
8
8