program apm;
type element=record
              x,y,z:longint;
            end;
var f,g:text;
    i,n,m,limita,rad1,rad2,suma,k:longint;
    v:array of element;
    sol,t:array of longint;
    bufin,bufout:array [1..1 shl 16] of char;
  procedure interschimbare (var a,b:element);
  var aux:element;
  begin
    aux:=a;
    a:=b;
    b:=aux;
  end;
  procedure cerne(k,l:longint);
  var son:longint;
  begin
    repeat
      son:=0;
      if k*2<=l then
        begin
          son:=k*2;
          if (k*2+1<=l)and(v[k*2+1].z>v[son].z) then
            son:=k*2+1;
          if v[k].z>=v[son].z then
            son:=0;
        end;
      if son>0 then
        begin
          interschimbare(v[k],v[son]);
          k:=son;
        end;
    until son=0;
  end;
  function radacina(x:longint):longint;
  begin
    while t[x]>0 do
      x:=t[x];
    radacina:=x;
  end;
begin
  assign(f,'apm.in');reset(f);
  assign(g,'apm.out');rewrite(g);
  settextbuf(f,bufin);settextbuf(g,bufout);
  readln(f,n,m);setlength(v,m+1);
  setlength(sol,n+1);setlength(t,m+1);
  for i:=1 to m do
    with v[i] do
      readln(f,x,y,z);
  limita:=m div 2;
  for i:=limita downto 1 do
    cerne(i,m);
  for i:=m downto 2 do
    begin
      interschimbare(v[1],v[i]);
      cerne(1,i-1);
    end;
  suma:=0;k:=0;
  for i:=1 to m do
    begin
      rad1:=radacina(v[i].x);
      rad2:=radacina(v[i].y);
      if rad1<>rad2 then
        begin
          t[rad2]:=rad1;
          inc(k);
          sol[k]:=i;
          suma:=suma+v[i].z;
        end;
    end;
  writeln(g,suma);
  writeln(g,k);
  for i:=1 to k do
    with (v[sol[i]]) do
      writeln(g,y,' ',x);
  close(f);close(g);
end.