type mch=record
     x,y,c:longint;
     end;
var f,g:text;
    n,m,cc,i,k,nr,op:longint;
    t:array[1..200000]of longint;
    a:array[1..400000] of mch;
    sel:array[1..400000] of boolean;
procedure load;
var i:longint;
begin
     assign(f,'apm.in'); reset(f);
     assign(g,'apm.out'); rewrite(g);
     readln(f,n,m);
     for i:=1 to m do readln(f,a[i].x,a[i].y,a[i].c);
end;
procedure heapup(k:longint);
var t:longint;
    aux:mch;
begin
     if k>1 then
     begin
          t:=k div 2;
          if a[t].c<a[k].c then
          begin
               aux:=a[t];
               a[t]:=a[k];
               a[k]:=aux;
               heapup(t);
          end;
     end;
end;
procedure buildh;
var i:longint;
begin
     for i:=2 to m do heapup(i);
end;
procedure heapdw(k,l:longint);
var x,o:longint;
    aux:mch;
begin
     if 2*k<=l then
     begin
          if 2*k+1<=l then x:=a[2*k+1].c
                      else x:=a[2*k].c-1;
          if a[2*k].c>x then o:=2*k
                        else o:=2*k+1;
          if a[k].c<a[o].c then
          begin
               aux:=a[k];
               a[k]:=a[o];
               a[o]:=aux;
               heapdw(o,l);
          end;
     end;
end;
procedure heapsort;
var aux:mch;
    l:longint;
begin
     l:=m;
     while l>1 do
     begin
          aux:=a[1];
          a[1]:=a[l];
          a[l]:=aux;
          dec(l);
          heapdw(1,l);
     end;
end;
procedure quick(s,d:longint);
var  aux:mch;
     x,i,j:longint;
begin
     i:=s; j:=d; x:=a[(s+d)div 2].c;
     repeat
          while x>a[i].c do inc(i);
          while x<a[j].c do dec(j);
          if i<=j then
          begin
               aux:=a[i]; a[i]:=a[j]; a[j]:=aux;
               inc(i); dec(j);
          end
     until i>j;
     if i<d then quick(i,d);
     if s<j then quick(s,j);
end;
begin
     load;
     buildh;
     heapsort;
     {quick(1,m);     }
     cc:=0;    nr:=0;
     fillchar(sel,sizeof(sel),false);
     for i:=1 to n do t[i]:=i;
     for i:=1 to m do
          if t[a[i].x]<>t[a[i].y] then
          begin
               inc(nr);      op:=t[a[i].x];
               for k:=1 to n do
                    if t[k]=op then t[k]:=t[a[i].y];
               cc:=cc+a[i].c;
               sel[i]:=true;
          end;
     writeln(g,cc); writeln(g,nr);
     for i:=1 to m do
          if sel[i]=true then writeln(g,a[i].x,' ',a[i].y);
     close(g);
end.