program apm;
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,b1: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 interclasare (st,dr,mijloc:longint);
var i,j,k:longint;
begin
 i:=st; j:=mijloc+1;   k:=0;
 while (i<=mijloc) and (j<=dr) do
  if v[i].c<v[j].c then
  begin
   k:=k+1; b1[k]:=v[i]; inc(i);
  end
  else
  begin
   k:=k+1; b1[k]:=v[j]; inc(j);
  end;
 if i<=mijloc then
 begin
  for j:=i to mijloc do
  begin
   k:=k+1; b1[k]:=v[j];
  end;
 end
 else
  if j<=dr then
  begin
   for i:=j to dr do
   begin
    inc(k); b1[k]:=v[i];
   end;
  end;
  k:=0;
  for i:=st to dr do
  begin
   inc(k); v[i]:=b1[k];
  end;
end;

procedure sort (st,dr:longint);
var mijloc:longint;
    aux:mi;
begin
 if dr-st<=1 then
 begin
  if v[st].c>v[dr].c then
  begin
   aux:=v[st]; v[st]:=v[dr]; v[dr]:=aux;
  end;
 end
 else
 begin
  mijloc:=(st+dr) div 2;
  sort (st,mijloc);
  sort (mijloc+1,dr);
  interclasare (st,dr,mijloc);
 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.