program arobe;
type natural=record
 l,c:longint;
end;
var f,g:text;
    n,m,i,j,lin,col,x,y,cost,nr:longint;
    c:array[1..20000,1..20000] of longint;
    min,k:longint;
    bufin,bufout:array [1..65000] of byte;
    viz:array[1..20000] of 0..1;
    sol:array[1..20000] of natural;

begin
 assign (F,'apm.in'); reset (f);
 assign (g,'apm.out'); rewrite (g);
 settextbuf (f,bufin);
 settextbuf (g,bufout);
 readln (f,n,m);
 for i:=1 to n do
  for j:=1 to n do
   if i=j then
    c[i,j]:=0
   else
    c[i,j]:=maxlongint;
 for i:=1 to m do
 begin
   readln (f,x,y,cost);
   c[x,y]:=cost;
   c[y,x]:=cost;
 end;
 nr:=0;
 cost:=0;  viz[1]:=1 ;
 for k:=1 to n-1 do
 begin
  min:=maxlongint;
  for i:=1 to n do
   for j:=1 to n do
    if (viz[i]=1) and (viz[j]=0) and (min>c[i,j]) then
    begin
     min:=c[i,j];
     lin:=i;
     col:=j;
    end;
    nr:=nr+1;
    cost:=cost+min;
    sol[nr].l:=lin; sol[nr].c:=col;
    viz[col]:=1;
 end;
 writeln (g,cost);
 writelN (g,nr);
 for i:=1 to nr do
  writeln (g,sol[i].l,' ',sol[i].c);
 close (F); close (g);
end.