Shortest Path Queries in a Directed Road Network

You are given a directed road network with n cities and m roads. Each road connects a pair of cities with a given length. Your task is to answer multiple queries about the shortest path distance between two cities. If there is no path between two cities, output -1.

Consider the following details:

• The road network is directed, i.e. a road from city u to city v does not guarantee a road from v to u.
• The length of a path is the sum of the lengths of its constituent roads. Formally, the distance of a path is defined as \(d = \sum_{i=1}^{k} w_i\), where \(w_i\) is the weight of the i-th road in the path.
• If no valid path exists between a given pair of cities \(a\) and \(b\), the answer is \(-1\).

Your solution needs to read input from stdin and print the results to stdout.

Input/Output Format: See the sections below.

inputFormat

The input is given via standard input and has the following format:

n m
u1 v1 w1
u2 v2 w2
... (m lines)
q
a1 b1
... (q lines)

• The first line contains two integers, n (the number of cities) and m (the number of roads).
• Each of the next m lines contains three integers u, v, w representing a road from city u to city v with length w.
• The next line contains an integer q, the number of queries.
• Each of the following q lines contains two integers a and b asking for the shortest path distance from city a to city b.

outputFormat

For each query, output the shortest path distance on a separate line. If no path exists between the queried cities, output -1.

## sample

6 6
0 1 2
1 2 3
2 3 1
3 4 5
4 5 2
1 5 10
3
0 5
2 4
0 4

12
6
11

</p>