Shortest Paths in a Fantasy Realm

In a magical world, villages are connected by enchanted roads, each road having a magical weight. However, due to disturbances by a fearsome dragon, some roads may not lead to a destination.

Your task is to help the villagers determine the shortest unblocked path from one village to another. Given a directed graph where each edge has a positive weight, you need to compute the shortest distance from a starting village to a target village for each query.

You can formulate the update condition in Dijkstra's algorithm as: $$\text{if } d[u] + w < d[v] \text{ then } d[v] = d[u] + w.$$

If no path exists between the given villages, output -1.

inputFormat

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

1. The first line contains two space-separated integers n and m, representing the number of villages (nodes) and the number of roads (edges) respectively.
2. The next m lines each contain three space-separated integers u, v, and w, which represent a directed road from village u to village v with weight w.
3. The following line contains an integer q, representing the number of queries.
4. The next q lines each contain two integers a and b, representing a query to find the shortest path from village a to village b.

outputFormat

For each query, output a single integer on its own line—the shortest distance from the start village to the target village. If no such path exists, output -1.

## sample

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

6
-1
-1

</p>