program mmire;
type ele=record
      x,y,c:integer;
      end;
var f,g:text;
     n,m,k,i:longint;
     s:int64;
     v:array[1..400000] of ele ;
     t,nr:array[1..400000] of longint;
procedure citire;
var i:longint;
begin
assign(f,'apm.in'); reset(f);
  readln(f,n,m);
  for i:=1 to m do
    readln(f,v[i].x,v[i].y,v[i].c);
close(f);
end;
function pivot(st,dr:longint):longint;
var i,j,di,dj,au:longint;
 aux:ele;
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;
           au:=di;
           di:=dj;
           dj:=au;

        end;
        i:=i+di;
        j:=j-dj;
    end;
    pivot:=i;
end;
 procedure sort(st,dr:longint);
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;
procedure apm;
var i,a,b:longint;
begin
  for i:=1 to m do
    t[i]:=-1;
    k:=0;
    s:=0;
 for  i:=1 to m do
   begin
     a:=radacina(v[i].x);
     b:=radacina(v[i].y);
     if a<>b then
       begin
          t[b]:=a;
          inc(k);
          nr[k]:=i;
          s:=s+v[i].c;
       end;
   end;
end;
begin
  citire;
  sort(1,m);
  apm;
  assign(g,'apm.out'); rewrite(g);
     writeln(g,s);
     writeln(g,k);
     for i:=1 to k do
       writeln(g,v[nr[i]].y,' ',v[nr[i]].x);
  close(g);
end.