program apm_pregatire_oni;

type    elem=record
          x,y:longint;
          c:integer;
end;

var     f,g:text;
        v:array[1..400000] of elem;
        b,t:array[1..200000] of longint;
        xx,yy,s,nr,k,n,m,i,j:longint;
        bufin,bufout:array[1..1 shl 16] of byte;

function  pivot(st,dr:longint):longint; inline;
var       di,dj,i,j,aux:longint;
          auxx:elem;
begin
  i:=st; j:=dr;
  di:=0; dj:=1;
  while i<j do
    begin
      if v[i].c>v[j].c then
        begin
          aux:=di;
          di:=dj;
          dj:=aux;
          auxx:=v[i];
          v[i]:=v[j];
          v[j]:=auxx;
        end;
      i:=i+di;
      j:=j-dj;
    end;
  pivot:=i;
end;

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

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;

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);
  sort(1,m);
  k:=0; s:=0;
  for i:=1 to m do
    begin
      xx:=radacina(v[i].x);
      yy:=radacina(v[i].y);
      if xx<>yy then
        begin
          t[yy]:=xx;
          inc(k);
          b[k]:=i;
          s:=s+v[i].c;
        end;
    end;
  writeln(g,s);
  writeln(g,k);
 for i:=1 to k do
    writeln(g,v[b[i]].x,' ',v[b[i]].y);
  close(f);
  close(g);
end.