Minimum Travel Time

You are given a network of N buildings and M bidirectional roads connecting them. Each road is associated with a travel time. Your task is to answer Q queries, where each query asks for the minimum travel time between two buildings. If no path exists between the two queried buildings, output -1.

The problem can be modeled as a graph where the buildings are nodes and the roads are weighted edges. The weight of an edge represents the travel time between two nodes. A useful approach is to use the Floyd–Warshall algorithm, which computes the shortest paths between all pairs of vertices. Recall that the update step in the algorithm is given by:

\[ d(i,j) = \min\{ d(i,j),\; d(i,k) + d(k,j) \} \]

inputFormat

The input is given from standard input and has the following format:

N M
u1 v1 t1
u2 v2 t2
... (M lines in total)
Q
x1 y1
x2 y2
... (Q lines in total)

Where:

• N is the number of buildings.
• M is the number of roads.
• Each road is represented by three integers u, v, and t: there is a road between building u and building v with travel time t.
• Q is the number of queries.
• Each query consists of two integers x and y, representing the start and destination buildings.

outputFormat

For each query, print the minimum travel time on a new line. If there is no path between two buildings, print -1.

## sample

5 6
1 2 3
1 3 1
2 3 1
3 4 6
3 5 4
4 5 2
3
1 4
2 5
1 5

7
5
5

</p>