All Pairs Shortest Path

The input consists of several test cases. Each test case starts with a line with three non-negative integers, $1 \le n \le 150$, $0 \le m \le 5000$ and $1 \le q \le 1000$, separated by single single spaces, where $n$ is the numbers of nodes in the graph, $m$ the number of edges and $q$ the number of queries. Nodes are numbered from $0$ to $n-1$. Then follow $m$ lines, each line consisting of three (space-separated) integers $u$, $v$ and $w$ indicating that there is an edge from $u$ to $v$ in the graph with weight $-1000 \le w \le 1000$. Then follow $q$ lines of queries, each consisting of two node numbers $u$ and $v$ (separated by a space), asking for the minimum distance from node $u$ to node $v$.

Input will be terminated by a line containing `0 0 0`, this line should *not* be
processed.

For each query, output a single line containing the minimum
distance from node $u$ to
$v$, or the word
`Impossible` if there is no path from
$u$ to $v$, or `-Infinity` if there are arbitrarily short paths
from $u$ to $v$. Print a blank line after each
test case.

Sample Input 1 | Sample Output 1 |
---|---|

4 3 4 0 1 2 1 2 2 3 3 1 0 2 1 2 3 0 3 3 2 1 2 0 1 100 0 1 1 0 0 0 0 |
4 2 Impossible 0 100 Impossible |