program apm;
type muchie=record
 x,y:longint; c:integer;
end;
var v,b:array[1..400000] of muchie;
    n,m,i,j,s,tx,ty:longint;
    aux:muchie;
    t,uz:array[1..200000] of longint;
    f,g:text;

function radacina(nod:longint):longint;
begin
 if t[nod]<0 then
  radacina:=nod
 else
  begin
   t[nod]:=radacina(t[nod]);
   radacina:=t[nod];
  end;
end;

procedure merge(st,dr,mijloc:longint);
var i,j,k:longint;
begin
 i:=st; j:=mijloc+1; k:=0;
 while (i<=mijloc) and (j<=dr) do
  if v[i].c<v[j].c then
   begin
    k:=k+1; b[k]:=v[i]; i:=i+1;
   end
  else
   begin
    k:=k+1; b[k]:=v[j]; j:=j+1;
   end;
 if i<=mijloc then
  begin
   for j:=i to mijloc do
    begin
     k:=k+1; b[k]:=v[j];
    end;
  end
 else
 if j<=dr then
  begin
   for i:=j to dr do
    begin
     k:=k+1; b[k]:=v[i];
    end;
  end;
 k:=0;
 for i:=st to dr do
  begin
   k:=k+1; v[i]:=b[k];
  end;
end;

procedure sort(st,dr:longint);
var mijloc:longint;
begin
 if dr-st<=1 then
  begin
   if v[st].c>v[dr].c then
    begin
     aux:=v[st]; v[st]:=v[dr]; v[dr]:=aux;
    end;
  end
 else
  begin
   mijloc:=(st+dr) div 2;
   sort(st,mijloc);
   sort(mijloc+1,dr);
   merge(st,dr,mijloc);
  end;
end;

begin
 assign(f,'grader_test7.in'); reset(f);
 assign(g,'apm.out'); rewrite(g);
 readln(f,n,m);
 for i:=1 to m do
  with v[i] do
   readln(f,x,y,c);
 sort(1,m);
 for i:=1 to m do
   t[i]:=-1;
 j:=0;
 for i:=1 to m do
  begin
    tx:=radacina(v[i].x);
    ty:=radacina(v[i].y);
    if tx<>ty then
     begin
      t[ty]:=tx;
      j:=j+1;
      uz[j]:=i;
      s:=s+v[i].c
     end;
   end;
 writeln(g,s);
 writeln(g,n-1);
 for i:=1 to j do
   writeln(g,v[uz[i]].x,' ',v[uz[i]].y);
 close(f);
 close(g);
end.