Decoding The Thief's Trail

Sherlock Holmes has received a mysterious note from the scene of a jewelry theft. The note appears to be a series of numbers, which Holmes suspects are related to weights in a directed graph. Your task is to help him decipher the note by finding the minimum weight path between pairs of nodes in the graph.

You are given a directed graph with \(n\) nodes and \(m\) weighted edges. Then, there are \(q\) queries; each query consists of two nodes \(u\) and \(v\). For each query, compute the shortest path from \(u\) to \(v\) using Dijkstra's algorithm. If there is no path from \(u\) to \(v\), output \(-1\).

Note: Input is read from the standard input (stdin) and output is written to the standard output (stdout).

inputFormat

The input consists of multiple lines:

• The first line contains two integers \(n\) and \(m\), which represent the number of nodes and edges respectively.
• The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\), representing a directed edge from node \(u\) to node \(v\) with weight \(w\).
• The following line contains a single integer \(q\) — the number of queries.
• The next \(q\) lines each contain two integers \(u\) and \(v\), indicating a query asking for the minimum path from node \(u\) to node \(v\).

All input is provided via standard input (stdin).

outputFormat

For each query, output a single integer on a separate line:

• If there exists a path from node \(u\) to node \(v\), output the minimum total weight of that path.
• If there is no such path, output \(-1\).

All output must be written to standard output (stdout).

## sample

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

9
5
-1

</p>