Shortest Path Distances in an Undirected Graph

You are given an undirected weighted graph with n nodes (numbered from 1 to n) and m edges. Each edge has an associated weight. Then, you are given q queries. Each query consists of a pair of nodes u and v. Your task is to determine the shortest path distance from u to v in the graph. If there is no path between the two nodes, output -1.

The shortest path distance is defined as the minimum sum of the weights along a path connecting u and v in the graph. You may assume that all edge weights are positive. In mathematical terms, if d(u,v) represents the distance between nodes u and v, then: \[ d(u,v)=\min_{P\in \mathcal{P}(u,v)} \sum_{(i,j)\in P} w(i,j) \] where \(\mathcal{P}(u,v)\) is the set of all paths connecting u to v and \(w(i,j)\) denotes the weight of edge (i,j).

Use Dijkstra's algorithm or any other correct method to solve the problem. The input is given in standard input (stdin) and your output should be written to standard output (stdout).

inputFormat

The first line contains two integers n and m denoting the number of nodes and number of edges respectively.

The next m lines each contain three integers u, v, and w representing an undirected edge between nodes u and v with weight w.

The following line contains a single integer q representing the number of queries.

Each of the next q lines contains two integers u and v which represent a query asking for the shortest distance between node u and node v.

outputFormat

For each query, output a single line containing the shortest path distance between the two nodes. If no path exists, output -1.

## sample

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

6
2
5

</p>