Minimum Travel Time Queries

You are given a network of n cities connected by m bidirectional roads. Each road connects two cities and has an associated travel time. Your task is to answer queries that ask you to determine the minimum travel time between two given cities. If there is no valid path between the two cities, output -1.

To solve this problem, you can use the Floyd–Warshall algorithm. This algorithm computes the shortest paths between every pair of vertices in a weighted graph. The update rule for the algorithm is given by the formula:

$$dist[i][j] = \min(dist[i][j],\; dist[i][k] + dist[k][j]) $$

where i and j are city indices and k is an intermediate city. Use this formula to update the travel times between cities.

inputFormat

The input is read from stdin and has the following format:

• 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 t, representing a road connecting city u and city v with travel time t. Roads are bidirectional.
• The following line contains an integer q – the number of queries.
• The next q lines each contain two integers: x and y, representing a query asking for the minimum travel time from city x to city y.

outputFormat

For each query, output the minimum travel time from city x to city y on a new line. If no path exists between the queried cities, output -1.

## sample

4 4
1 2 5
1 3 10
2 3 2
3 4 1
3
1 4
2 3
1 3

8
2
7

</p>