Shortest Travel Time

You are given a network representing houses and roads. There are n houses and m bidirectional roads connecting them. Each road connects two houses and has an associated travel time.

Your task is to compute the shortest travel time between a set of critical pairs of houses. For a given critical pair \( (a, b) \), the answer is the least cumulative travel time from house \(a\) to house \(b\). If there is no path between \(a\) and \(b\), output -1.

The travel time along a path is the sum of the weights of the roads used. Formally, if a path consists of roads with weights \( w_1, w_2, \dots, w_k \), then its travel time is

\( T = \sum_{i=1}^{k} w_i \).

This problem is a classic application of Dijkstra's algorithm.

inputFormat

The input is given via standard input (stdin):

• The first line contains two integers \( n \) and \( m \) denoting the number of houses and the number of roads.
• The next \( m \) lines each contain three integers \( u \), \( v \), \( w \), indicating there is a road between house \( u \) and house \( v \) with travel time \( w \).
• The next line contains a single integer \( k \), the number of critical pairs.
• The following \( k \) lines each contain two integers \( a \) and \( b \), representing a critical pair of houses.

outputFormat

For each critical pair, output a single line with the shortest travel time from \( a \) to \( b \). If house \( b \) is unreachable from \( a \), output -1.

## sample

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

7
5
9

</p>