Shortest Paths in a Directed Graph

You are given a directed graph with n nodes and m edges. Each edge is associated with a non-negative weight. Your task is to compute the shortest path from a given source node s to a destination node d using Dijkstra's algorithm.

If there is no path from s to d, output \(-1\). The mathematical formulation is as follows: for each vertex \(v\), the distance \(d(v)\) is given by

\[ d(v) = \min_{(u,v) \in E} \{ d(u) + w(u,v) \} \]

where \(w(u,v)\) is the weight of the edge from node \(u\) to node \(v\), and \(d(s)=0\).

inputFormat

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

The following m lines each contain three integers u, v, and w, indicating there is a directed edge from node u to node v with weight w.

The next line contains an integer T, the number of queries. Each of the following T lines contains two integers s and d, representing the source and destination nodes for which you must compute the shortest distance.

outputFormat

For each query, output a single line containing the shortest distance from s to d. If there is no path, output -1.

## sample

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

6
4
-1

</p>