program prim;
const inf=9999999;
type
lista=^date;
date=record
m,cost:longint;
next:lista;
end;
tabel=array[0..200001] of lista;
tab=array[0..200001] of longint;
tabb=array[0..400001] of longint;
var
t:tabel; fr,d,tata,pos,solx,soly,last:tab; heap:tabb;
n,m,x,y,z,i,j,k,nr:longint; a:lista;
f1,f2:text;
procedure swap(var a,b:longint);
var aux:longint;
begin aux:=a; a:=b; b:=aux; aux:=pos[a]; pos[a]:=pos[b]; pos[b]:=aux; end;
procedure heapup(v:longint);
var k:longint;
begin
k:=heap[v];
while (v>1) and (d[heap[v div 2]]>d[heap[v]]) do begin
swap(heap[v],heap[v div 2]);
v:=v div 2;
end;
heap[v]:=k;
end;
procedure heapdown(v:longint);
var w:longint;
begin
w:=v*2;
while w<=k do begin
if (w+1<=k) and (d[heap[w]]>d[heap[w+1]]) then w:=w+1;
if d[heap[v]]>d[heap[w]] then swap(heap[v],heap[w]);
v:=w; w:=w*2;
end;
end;
procedure delheap;
begin
swap(heap[1],heap[k]);
nr:=nr+1; last[nr]:=heap[k];
fr[heap[k]]:=1; k:=k-1;
heapdown(1);
end;
begin
assign (f1,'apm.in');
assign (f2,'apm.out');
reset (f1);
rewrite (f2);
readln (f1,n,m);
for i:=1 to m do begin
readln (f1,x,y,z);
new(a); a^.m:=x; a^.cost:=z; a^.next:=t[y]; t[y]:=a;
new(a); a^.m:=y; a^.cost:=z; a^.next:=t[x]; t[x]:=a;
end;
for i:=1 to n do begin d[i]:=inf; heap[i]:=i; pos[i]:=i; end;
fr[1]:=1; d[1]:=0; k:=n; nr:=0;
repeat
a:=t[heap[1]]; x:=heap[1]; delheap;
if nr>1 then begin solx[nr-1]:=last[nr-1]; soly[nr-1]:=last[nr]; end;
while a<>nil do begin
if (a^.cost<d[a^.m]) and (fr[a^.m]=0) then begin
d[a^.m]:=a^.cost; heapup(pos[a^.m]);
end;
a:=a^.next;
end;
until k=0;
k:=0;
for i:=1 to n do k:=k+d[i];
writeln (f2,k);
writeln (f2,nr);
for i:=1 to nr-1 do writeln (f2,solx[i],' ',soly[i]);
close (f1);
close (f2);
end.