Shortest Path Queries

You are given a network of cities connected by bidirectional roads. Each road has an associated travel time. Your task is to answer several queries about the shortest travel time between pairs of cities. If there is no valid path connecting the queried cities, output IMPOSSIBLE.

The problem can be formally described as follows: Given n cities and m roads, each road connecting two cities u and v with a travel time t, compute for each query the minimum travel time from a source city a to a destination city b. The update step in the Floyd–Warshall algorithm is given by the formula: \(d[i][j] = \min(d[i][j],\; d[i][k] + d[k][j])\).

It is guaranteed that cities are numbered from 1 to n. Roads are undirected and there might be multiple roads between two cities; in such a case, consider the road with the minimum travel time.

inputFormat

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

• The first line contains two integers n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ n(n-1)/2), representing the number of cities and roads.
• The next m lines each contain three integers u, v and t (1 ≤ u, v ≤ n, 1 ≤ t ≤ 10^5), representing a road between cities u and v with travel time t.
• The next line contains an integer q (q ≥ 1), the number of queries.
• Each of the next q lines contains two integers a and b, representing a query to find the shortest travel time from city a to city b.

outputFormat

For each query, output the shortest travel time between the given cities. If there is no path connecting the cities, output IMPOSSIBLE. Each answer should be printed on a new line to standard output (stdout).

## sample

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

3
2

</p>