Shortest Travel Time Queries

You are given a directed weighted graph representing a city's road network. The graph has n intersections and m roads. Each road is defined by three integers U, V, and T representing a road from intersection U to intersection V with travel time T. You are also given q queries, each asking for the shortest travel time from a starting intersection A to a destination intersection B.

If there is no path from A to B, output \(-1\). Note that if A equals B, the shortest travel time is \(0\).

Input Format: The first line contains two integers \(n\) and \(m\). The next \(m\) lines each contain three integers \(U\), \(V\), and \(T\). Then follows a line with a single integer \(q\), and finally \(q\) lines follow, each containing two integers \(A\) and \(B\).

Output Format: For each query, output the shortest travel time on a new line.

inputFormat

The input is read from stdin in the following format:

n m
U1 V1 T1
U2 V2 T2
... (m lines total)
q
A1 B1
A2 B2
... (q lines total)

outputFormat

For each query, print the shortest travel time from A to B on a separate line. If there is no path from A to B, print -1.

## sample

5 6
1 2 4
1 3 2
3 2 1
2 4 7
3 4 4
4 5 1
3
1 5
2 1
3 4

7
-1
4

</p>