Problem N
Minimum Spanning Tree

Input

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.

Output

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.

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