Shortest Path in a Weighted Graph

A mapping application requires an efficient algorithm to compute the shortest distances between landmarks in a weighted graph. Given an undirected weighted graph with n nodes and m edges, your task is to answer several queries asking for the shortest path between two nodes.

If there is no path between the two nodes, the output should be -1. The update equation for the shortest path is given by:

\( d(v) = \min\bigl(d(v),\ d(u)+w(u,v) \bigr) \)

Implement the algorithm such that it processes multiple queries efficiently.

inputFormat

The input is given in the following format via standard input:

• The first line contains two integers n and m representing the number of nodes and the number of edges respectively.
• The next m lines each contain three integers u, v, and w, describing an edge between nodes u and v with weight w. The graph is undirected.
• The following line contains an integer q denoting the number of queries.
• Each of the next q lines contains two integers a and b, where each query asks for the shortest distance from node a to node b.

outputFormat

For each query, print a single line with the shortest path distance from the source node to the destination node. If there is no path between them, print -1.

## sample

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

4
4
2

</p>