uses crt;  type rec=record
          a,b,c:longint;
        end;
     vek=array[1..400000] of rec;
     vet=array[1..200000] of longint;
var v:vek;
    cs:vet;
    i,j,k,l,m,n,ossz:longint;
    f,g:text;
    s:string;
procedure quick(bal,jobb:longint);
 var i,j,kozep:longint;
     temp:rec;
  begin
   i:=bal;
   j:=jobb;
   kozep:=v[(i+j) div 2].c;
   while i<=j do
    begin
     while v[i].c<kozep do inc(i);
     while v[j].c>kozep do dec(j);
     if i<=j then begin
                   temp:=v[i];
                   v[i]:=v[j];
                   v[j]:=temp;
                   inc(i);
                   dec(j);
                  end;
    end;
   if bal<j then quick(bal,j);
   if i<jobb then quick(i,jobb);
  end;
begin
 clrscr;
 assign(f,'apm.in');
 reset(f);
 readln(f,n,m);
 for i:= 1 to m do
  readln(f,v[i].a,v[i].b,v[i].c);
 close(f);
 quick(1,m);
 for i:= 1 to n do cs[i]:=i;
 assign(f,'apm.ke');
 rewrite(f);
 ossz:=0;
 i:=1;
 while i<=m do
  begin
   if cs[v[i].a]<>cs[v[i].b] then  begin
     l:=cs[v[i].b];
     for j:= 1 to n do
        begin
         if cs[j]=l then cs[j]:=cs[v[i].a];
        end;
   writeln(f,v[i].a,' ',v[i].b);
   ossz:=ossz+v[i].c; end;
   inc(i);
  end;
 close(f);
 assign(g,'apm.out');
 rewrite(g);
 assign(f,'apm.ke');
 reset(f);
 writeln(g,ossz);
 writeln(g,n-1);
 while not eof(f) do
  begin
   readln(f,s);
   writeln(g,s);
  end;
 close(g);
 close(f);
end.