Description

Country A has $n$ cities, numbered from $1$ to $n$, and there are $m$ bidirectional roads between the cities. Each road has a weight limit for vehicles, referred to as the load limit.

There are $q$ trucks transporting goods. The drivers want to know, without exceeding any road's weight limit, the maximum weight each truck can carry.

Input Format

The first line contains two integers $n,m$ separated by a single space, indicating that Country A has $n$ cities and $m$ roads.

Each of the next $m$ lines contains three integers $x, y, z$, separated by single spaces, indicating there is a road from city $x$ to city $y$ with weight limit $z$.
Note: $x \neq y$, and there may be multiple roads between two cities.

The next line contains an integer $q$, meaning there are $q$ trucks that need to transport goods.

Then follow $q$ lines, each containing two integers $x,y$ separated by a space, indicating a truck needs to transport goods from city $x$ to city $y$, with $x \neq y$ guaranteed.

Output Format

Output $q$ lines, each with an integer, indicating the maximum load for each truck.
If a truck cannot reach the destination, output $-1$.

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

3
-1
3

Hint

For $30\%$ of the testdata, $1 \le n < 1000$, $1 \le m < 10,000$, $1\le q< 1000$.

For $60\%$ of the testdata, $1 \le n < 1000$, $1 \le m < 5\times 10^4$, $1 \le q< 1000$.

For $100\%$ of the testdata, $1 \le n < 10^4$, $1 \le m < 5\times 10^4$, $1 \le q< 3\times 10^4$, $0 \le z \le 10^5$.

Translated by ChatGPT 5