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 of array of longint;
    min,k:longint;
    viz:array of 0..1;
   sol:array of natural;
begin
 assign (F,'apm.in'); reset (f);
 assign (g,'apm.out'); rewrite (g);
 readln (f,n,m);
 setlength (c,n+1,n+1);
 setlengtH (viz,n+1); setlength (sol,n+1);
 for i:=1 to n-1 do
  for j:=i+1 to n do
  begin
    c[i,j]:=maxlongint;
    c[j,i]:=maxlongint;
  end;
 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.