program apm_PENTRU_MARIA;
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;
    bufin,bufout:array[1..65535] of byte;
    t,uz:array[1..200000] of longint;
    f,g:text;

function radacina(nod:longint):longint; //stii tu ce face functia asta :))
begin
 if t[nod]<0 then
  radacina:=nod
 else
  begin
   t[nod]:=radacina(t[nod]);
   radacina:=t[nod];
  end;
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);
 settextbuf(f,bufin);
 settextbuf(g,bufout);
 readln(f,n,m);
 for i:=1 to m do
  with v[i] do
   readln(f,x,y,c);
 qsort(1,m);
 for i:=1 to n 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 //daca x si y fac parte din componente conexe diferite atunci...x si y trebuie sa faca parte din componente conexe diferite pt ca altfel ai obtine un ciclu
     begin
      t[ty]:=tx;
      j:=j+1;
      uz[j]:=i;//aici marchezi ce muchie ai folosit..o sa ai nevoie la afisare
      s:=s+v[i].c // actualizezi costul minim
     end;
   end;
 writeln(g,s);// afisezi costul minim
 writeln(g,n-1); //nr maxim de muchii pe care il poate avea arborele partial de cost minim ...intotdeauna este n-1 :P
 for i:=1 to j do
   writeln(g,v[uz[i]].x,' ',v[uz[i]].y);  //afisezi muchiile folosite in construirea arborelui
 close(f);
 close(g);
end.