const infile='apm.in';
  outfile='apm.out';
  maxn=200003;
  maxm=400003;
type muchie=record  e1,e2,cost:longint; end;
var g:array[1..maxm]of muchie;
  a,tata,niv:array[1..maxn]of longint;
  n,m,vf,capm:longint;

 procedure citire;
 var i,j,k,c:longint;
 begin
   assign(input,infile); reset(input); readln(n,m);
   for k:=1 to m do readln(g[k].e1,g[k].e2,g[k].cost);
   close(input);
 end;

 procedure schimba(x,y:longint);
 var v:muchie;
 begin
   v:=g[x]; g[x]:=g[y]; g[y]:=v;
 end;

 procedure qsort(st,dr:longint);
 var i,j:longint;
   x:muchie;
 begin
   if(st<dr)then  begin
     i:=st; j:=dr; x:=g[st];
     while(i<j)do  begin
       while(i<j)and(g[j].cost>=x.cost)do  dec(j);
       g[i]:=g[j];
       while(i<j)and(g[i].cost<=x.cost)do  inc(i);
       g[j]:=g[i];
       end;
     g[i]:=x;
     qsort(st,i-1); qsort(i+1,dr);
     end;
 end;

 function find(x:longint):longint;
 var y,r,t:longint;
 begin
   r:=x; while(tata[r]<>0)do r:=tata[r];
   y:=x; while(y<>r)do begin t:=tata[y]; tata[y]:=r; y:=t; end;
   find:=r;
 end;

 procedure union(x,y:longint);
 begin
   if(niv[x]>niv[y])then tata[y]:=x
   else tata[x]:=y;
   if(niv[x]=niv[y])then inc(niv[y]);
 end;

 procedure kruskal;
 var i,j,k:longint;
 begin
   qsort(1,m);
   vf:=0;
   for k:=1 to m do begin
     i:=find(g[k].e1); j:=find(g[k].e2);
     if(i<>j)then begin
       inc(vf); a[vf]:=k;
       inc(capm,g[k].cost); union(i,j); end;
     end;
 end;

 procedure afisare;
 var i:longint;
 begin
   assign(output,outfile); rewrite(output); writeln(capm); writeln(vf);
   for i:=1 to vf do writeln(g[a[i]].e1,' ',g[a[i]].e2);
   close(output);
 end;

begin
citire; kruskal; afisare;
end.