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

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

function pivot(st,dr:integer):integer;
var i,j,di,dj,AUX2:integer;
    aux:lamate;
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;
         aux2:=di;
         di:=dj;
         dj:=AUX2;
        end;
      i:=i+di;
      j:=j-dj;
    end;
 pivot:=i;
end;


procedure sort(st,dr:integer);
var p:integer;
begin
  if st<dr then
    begin
     p:=pivot(st,dr);
     sort(st,p-1);
     sort(p+1,dr);
    end;
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(1,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[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.