Shortest Travel Time

You are given a directed weighted graph that represents buildings and the roads connecting them. There are n buildings numbered from 1 to n and m directed roads. Each road is given by three integers u, v, and t, which represent a road from building u to building v with travel time t.

You will also receive q queries. Each query contains two integers s and d and asks for the shortest travel time from building s to building d. If there is no path from s to d, output -1.

This problem is essentially a single-source shortest path problem in a weighted directed graph. One common approach is to use Dijkstra's algorithm. The total cost of a path P is given by:

$$ \sum_{(u,v) \in P} t(u,v) $$

Compute and output the shortest cost for each query accordingly.

inputFormat

The input is read from standard input and is formatted as follows:

• The first line contains two integers n and m — the number of buildings and roads.
• The next m lines each contain three integers u, v, and t, describing a road from building u to building v with travel time t.
• The following line contains one integer q — the number of queries.
• The next q lines each contain two integers s and d, representing the start and destination buildings.

outputFormat

For each query, output the shortest travel time from the given start building to the destination building on a separate line. If there is no path, output -1.

## sample

5 5
1 2 10
2 3 20
3 4 30
4 5 40
1 3 100
3
1 5
3 1
3 4

100
-1
30

</p>