program mmire;
type ele=record
      x,y:longint;
      c:integer;
      end;
var f,g:text;
     n,m,k,i:longint;
     s:int64;
     v:array[1..400000] of ele ;
     t,nr:array[1..200000] of longint;
     bufin,bufout:array[1.. 1 shl 16] of byte;
procedure citire;
var i:longint;
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 m do
    readln(f,v[i].x,v[i].y,v[i].c);
close(f);
end;
///// quick_sort...//////////
function pivot(st,dr:longint):longint;
var i,j,di,dj,au:longint;
 aux:ele;
begin
  i:=st; j:=dr; di:=0; dj:=1;
  while i<j do
    begin
       if v[i].c>v[j].c then
        begin
          aux:=v[i];
          v[i]:=v[j];
          v[j]:=aux;
           au:=di;
           di:=dj;
           dj:=au;

        end;
        i:=i+di;
        j:=j-dj;
    end;
    pivot:=i;
end;
 procedure sort(st,dr:longint);
var p:longint;
begin
 if st< dr then
   begin
     p:=pivot(st,dr);
     sort(st,p-1);
     sort(p+1,dr);
   end;
end;
/////////// end_quick_sort..../////////////
function radacina(nod:longint):longint;
begin
 if t[nod]<>0 then
  radacina:=radacina(t[nod])
  else
 radacina:=nod;
end;
//////**heap-sort..........//////////
procedure swap(var a,b:ele);
var aux:ele;
begin
  aux:=a ;
  a:=b;
  b:=aux;
end;
procedure down(mm,o:longint);
var l,r,son:longint;
begin
repeat
   son:=0;
   l:=2*o;
   r:=2*o+1;
   if l<=mm then
   begin
      son:=l;
    if (r<=mm) and (v[r].c>v[l].c )  then
       son:=r;
    if v[son].c<=v[o].c then
      son:=0;
   end;
   if son<>0 then
    begin
       swap(v[son],v[o]);
       o:=son;
    end;
until son=0;
end;
procedure built(mm:longint);
var i:longint;
begin
  for i:=mm div 2 downto 1 do
      down(mm,i);
end;
procedure sortare(mm:longint);
var i:longint;
begin
        built(mm);
  for i:= mm downto 2 do
    begin
      swap(v[i],v[1]);
      down(i-1,1);
    end;
end;

/////////// end_heap_sort.....///////////
procedure apm;
var i,a,b:longint;
begin
    k:=0;
    s:=0;
 for  i:=1 to m do
   begin
     a:=radacina(v[i].x);
     b:=radacina(v[i].y);
     if a<>b then
       begin
          t[b]:=a;
          inc(k);
          nr[k]:=i;
          s:=s+v[i].c;
       end;
   end;
end;
begin
  citire;
  sortare(m);
  apm;
     writeln(g,s);
     writeln(g,k);
     for i:=1 to k do
       writeln(g,v[nr[i]].y,' ',v[nr[i]].x);
  close(g);
end.