Shortest Path Queries

You are given an undirected weighted graph. Your task is to answer several queries on the shortest path between two nodes in the graph.

The graph has n nodes and m edges. Each edge is specified by three integers u, v, and w which represent an undirected edge between nodes u and v with weight w. For each query, given two nodes S and E, you need to compute the shortest distance from S to E. If no such path exists, output -1.

Note: The graph might contain multiple components.

Input/Output: All input is provided via standard input and your results should be printed to standard output.

inputFormat

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

Then m lines follow, each containing three integers u, v, and w, indicating an undirected edge between u and v with weight w.

The next line contains an integer q, the number of queries.

Then q lines follow, each with two integers S and E, representing a query for the shortest path from node S to node E.

outputFormat

For each query, output a single integer representing the shortest distance from S to E. If there is no path between S and E, output -1. Each answer should be printed on a separate line in the order of the queries.## sample

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

6
1
3