Minimum Travel Cost

You are given a kingdom with \(N\) cities and \(M\) directed roads. Each road from city \(u\) to city \(v\) has an associated travel cost \(w\). Your task is to calculate the minimum travel cost from a source city to a destination city for multiple queries. If there is no valid route between two cities, output \(-1\).

You can solve this problem using the Floyd-Warshall algorithm to compute the shortest paths between all pairs of cities.

Note: The cities are numbered from 1 to \(N\).

inputFormat

The input is given via standard input (stdin) and is formatted as follows:

N M
u1 v1 w1
u2 v2 w2
... (M lines)
K
q1_u q1_v
q2_u q2_v
... (K lines)

where:

• \(N\) is the number of cities.
• \(M\) is the number of directed roads.
• Each road is described by three integers: \(u_i\) (starting city), \(v_i\) (destination city), and \(w_i\) (cost).
• \(K\) is the number of queries.
• Each query consists of two integers which are the source and the destination city.

outputFormat

For each query, output a single line containing the minimum travel cost from the source city to the destination city. If there is no path between them, output \(-1\).

## sample

4 4
1 2 100
2 3 200
3 4 300
1 4 1000
2
1 4
2 4

600
500

</p>