Minimum Spanning Tree

The input consists of several test cases. Each test case starts with a line with two non-negative integers, $1 \le n \le 20\, 000$ and $0 \le m \le 30\, 000$, separated by a single space, where $n$ is the numbers of nodes in the graph and $m$ is the number of edges. 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 between $u$ and $v$ in the graph with weight $-20\, 000 \le w \le 20\, 000$. Edges are undirected.

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

For every test case, if there is no minimum spanning tree,
then output the word `Impossible` on a
line of its own. If there is a minimum spanning tree, then you
first output a single line with the cost of a minimum spanning
tree. On the following lines you output the edges of a minimum
spanning tree. Each edge is represented on a separate line as a
pair of numbers, $x$ and
$y$ (the endpoints of the
edge) separated by a space. The edges should be output so that
$x < y$ and should be
listed in the lexicographic order on pairs of integers.

If there is more than one minimum spanning tree for a given graph, then any one of them will do.

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

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