Minimum Travel Time

You are given a network of buildings and roads connecting them. There are n buildings and m roads. Each road connects two buildings and has an associated travel time. The graph is undirected and all travel times are non-negative. For each query, you need to find the minimum travel time between a given pair of buildings. If there is no path between the buildings, output -1.

Consider using Dijkstra's algorithm which runs in $O((E+V)\log V)$ time to solve each query efficiently.

inputFormat

The input is given via standard input (stdin) in the following format:

• The first line contains two integers n and m, where n is the number of buildings and m is the number of roads.
• The next m lines each contain three integers u, v, and w. Each line represents a road connecting building u and building v with a travel time w.
• The following line contains an integer q, the number of queries.
• The next q lines each contain two integers u and v, representing a query asking for the shortest travel time from building u to building v.

outputFormat

For each query, output the minimum travel time on a separate line. If there is no path between the given buildings, output -1.## sample

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

3
8
4