Subway Minimal Travel Time

You are given a subway system with n stations and m subway lines. Each line connects two stations and has an associated travel time.

For each query, determine the minimal travel time between two given stations. If there is no path connecting the stations, output -1.

You can solve this problem using the Floyd–Warshall algorithm. The recurrence used is given by the formula:

$$d[i][j] = \min\{ d[i][j], d[i][k] + d[k][j] \}$$

where d[i][j] is the shortest known distance from station i to station j.

inputFormat

The first line contains two integers n and m, representing the number of stations and the number of subway lines, respectively.

The next m lines each contain three integers u, v and w, indicating there is a subway line between stations u and v with travel time w.

The following line contains an integer q, the number of queries.

Then, q lines follow, each containing two integers a and b representing a query asking for the minimum travel time from station a to station b.

outputFormat

Output q lines. Each line should contain a single integer representing the minimum travel time between the query stations. If there is no valid path, output -1.

## sample

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

7
5
4

</p>