Shortest Paths in an Undirected Graph

Given an undirected graph with n vertices and m weighted edges, your task is to answer q queries regarding the shortest path between pairs of vertices. For each query, determine the minimum distance between vertex u and vertex v. If there is no path between them, output -1.

The shortest path distance between two vertices is defined by the formula:

\(d(u,v)=\min_{P\;:\;u\rightarrow v}\sum_{e \in P} w(e)\)

Note that the graph is undirected and may contain self-loops. All edge weights are non-negative.

inputFormat

The input is given in the following format:

 n m
 u1 v1 w1
 u2 v2 w2
 ...
 um vm wm
 q
 u1 v1
 u2 v2
 ...
 uq vq

Here, the first line contains two integers n and m, the number of vertices and edges respectively. The next m lines each contain three integers u, v, and w, representing an undirected edge between vertices u and v with weight w. The integer q denotes the number of queries, followed by q lines each containing two integers representing a query between a pair of vertices.

outputFormat

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

## sample

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

9
7
6

</p>