Shortest Paths in Geeklandia

You are given a network of cities connected by bidirectional roads. Each road connects two different cities and has an associated weight representing the travel cost between them. Your task is to compute the shortest path between given pairs of cities.

To solve this problem, you should implement the Floyd–Warshall algorithm, whereby the distance d(i,j) between any two cities i and j is computed using the recurrence

\( d(i,j) = \min\{d(i,j),\; d(i,k) + d(k,j)\} \)

If two cities are not connected through any path, output -1 for that query.

Input from STDIN and output to STDOUT.

inputFormat

The first line contains an integer n (2 ≤ n ≤ 100) representing the number of cities.

The second line contains an integer m indicating the number of roads.

Each of the next m lines contains three integers u v w representing a road between cities u and v with cost w. It is guaranteed that the road is bidirectional.

The next line contains an integer q representing the number of queries.

Each of the next q lines contains two integers a b specifying a query to find the shortest distance between city a and city b.

outputFormat

For each query, output a single line with the shortest distance between the given pair of cities. If there is no path connecting the two cities, output -1.

## sample

4
4
1 2 4
1 3 2
2 3 1
3 4 7
3
1 4
2 4
1 1

9
8
0

</p>