Shortest Path in a City Network

You are given a network of n cities connected by bidirectional roads. Each road between two cities u and v has a distance d. You are also given several queries where each query asks for the shortest distance between a pair of cities. If no path exists between a queried pair, output -1.

The task is to compute the shortest path between the queried cities using an efficient algorithm (for example, Dijkstra's algorithm). The problem input is provided via standard input (stdin) and the results should be output via standard output (stdout).

The mathematical formulation of the shortest path between two cities s and t can be described using the following formula in LaTeX:

$$ d(s,t)=\min_{\text{paths }P:\, s\to t} \sum_{(u,v)\in P} w(u,v) $$

If no such path exists, then \( d(s,t) = -1 \).

inputFormat

The input is given via stdin in the following format:

1. An integer n representing the number of cities.
2. An integer m representing the number of roads.
3. m lines follow, each containing three integers u v d where u and v are cities connected by a road and d is the distance of that road.
4. An integer q representing the number of queries.
5. q lines follow, each containing two integers s t representing a query from city s to city t.

Constraints: Cities are numbered from 1 to n. It is guaranteed that the input is valid.

outputFormat

For each query, output a single line containing the shortest distance between the two cities. If there is no valid path, output -1.

The output should be written to stdout.

## sample

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

7
5

</p>