Shortest Path Queries in an Undirected Graph

This problem involves processing multiple queries to determine the shortest path delays in an undirected weighted graph. You are given a graph with N nodes and M edges. Each edge is represented by a triple (U, V, W), indicating an undirected edge between nodes U and V with weight W. After constructing the graph, you need to answer Q queries, where each query asks for the shortest path from a source node S to a target node T.

The answer for each query should be the minimum total weight along a valid path from S to T. If there is no path connecting the nodes, output -1. The shortest path computation should be performed using Dijkstra's algorithm.

Note: All nodes are 1-indexed.

inputFormat

The input is given from stdin in the following format:

N M
U1 V1 W1
U2 V2 W2
... (M lines total)
Q
S1 T1
S2 T2
... (Q lines total)

Where:

• N is the number of nodes.
• M is the number of edges.
• Each of the next M lines contains three integers U, V, W representing an edge.
• Q is the number of queries.
• Each of the next Q lines contains two integers S and T representing a query from node S to node T.

outputFormat

The output should be written to stdout. For each query, print a single integer on a new line denoting the shortest path distance from node S to node T. If no path exists, output -1.

## sample

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

13
3
6

</p>