program aaaa;
type mi=record
     x,y,c:longint;
     end;
var f,g:text;
    n,m,i,j,s,a,b,k:longint;
    ok:boolean;
    aux:mi;
    v:array[1..200005] of mi;
    t,nr:array[1..200005] of longint;

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


procedure sort(m2:longint);
  var k:longint;
  aux:mi;
    begin
     k:=m2;
      repeat
        ok:=true;
        for i:=1 to k-1 do
          if v[i].c>v[i+1].c then
            begin
              aux:=v[i];
              v[i]:=v[i+1];
              v[i+1]:=aux;
              ok:=false;
            end;
        k:=k-1;

      until ok;
    end;
begin
assign(f,'apm.in'); reset(f);
assign(g,'apm.out'); rewrite(g);
  readln(f,n,m);
    for i:=1 to m do
      begin
         readln(f,v[i].x,v[i].y,v[i].c);
      end;
    sort(m);

      k:=0;
    for i:=1 to m do
      t[i]:=-1;
    for i:=1 to m do
      begin
        a:=tata(v[i].x);
        b:=tata(v[i].y);
          if a<>b then
            begin
           {  t[a]:=t[a]+t[b];  }
              t[b]:=a;
              k:=k+1;
              nr[k]:=i;
              s:=s+v[i].c;
            end;
      end;
    writeln(g,s);
    writeln(g,k);
    for i:=1 to k do
      writeln(g,v[nr[i]].y,' ',v[nr[i]].x);
close(f);
close(g);
end.