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