Shortest Path Queries in Directed Graphs

You are given a directed weighted graph with n vertices and m edges. Each edge is represented by three integers u, v, and w indicating a directed edge from vertex u to vertex v with weight w. You are then given several queries. For each query, which consists of two integers, s and t, your task is to compute the length of the shortest path from vertex s to vertex t. If there is no path from s to t, output -1.

The shortest path length, if it exists, is defined as:

$$d(s,t)=\min_{p:s\to t}\sum_{e\in p}w_e,$$

where the path p is any sequence of edges from s to t and w_e is the weight of edge e.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers n and m: the number of vertices and the number of edges.
• The next m lines each contain three integers u, v, and w, representing a directed edge from vertex u to vertex v with weight w.
• The following line contains an integer q, the number of queries.
• The next q lines each contain two integers s and t, representing a query to find the shortest path from vertex s to vertex t.

outputFormat

For each query, output the length of the shortest path from s to t on a separate line. If there is no path, output -1.

The output should be written to standard output (stdout).

## sample

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

-1
7

</p>