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
 while t[nod]<>0 do
        nod:=t[nod];
 radacina:=nod;
end;

function pivot(st,dr:longint):longint;
var di,dj,d,i,j:longint;
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;
                d:=di;
                di:=dj;
                dj:=d;
        end;
        i:=i+di;
        j:=j-dj;
 end;
 pivot:=i;
end;

procedure qsort(st,dr:longint);
var p:longint;
begin
 if st<dr then
 begin
        p:=pivot(st,dr);
        qsort(st,p-1);
        qsort(p+1,dr);
 end;
end;

begin
 assign(f,'apm.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);
 qsort(1,m);
 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.