program apm;
type hacking=record
 x,y,cost:longint;
end;
var f,g:text;
    n,m,i:longint;
    v:array[1..400000] of hacking;
    nr,t:array[1..400000] of longint;
    b:array[1..400000] of hacking;
    suma,k,a,b1:longint;
    retine:array[1..400000] of longint;
    bufin,bufout:array[1..65000] of byte;

procedure interclasare (st,dr,mijloc:longint);
var i,j,k,i1:longint;
begin
 k:=0; i:=st; j:=mijloc+1;
 while (i<=mijloc) and (j<=dr) do
  if v[i].cost<v[j].cost then
  begin
   inc(k); b[k]:=v[i]; inc(i);
  end
  else
  begin
   inc(k); b[k]:=v[j]; inc(j);
  end;
  for i1:=i to mijloc do
  begin
   inc(k); b[k]:=v[i1];
  end;
  for i1:=j to dr do
  begin
   inc(k); b[k]:=v[i1];
  end;
  k:=0;
  for i:=st to dr do
  begin
   inc(k); v[i]:=b[k];
  end;
end;

procedure sort (st,dr:longint);
var mijloc:longint;
    aux:hacking;
begin
 if dr-st<=1 then
 begin
  if v[st].cost>v[dr].cost 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;

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;

begin
 assign (f,'apm.in'); reset (f);
 assign (g,'apm.out'); rewrite (g);
 settextbuf (f,bufin);
 settextbuf (g,bufout);
 readln (f,n,m);
 for i:=1 to m do
 begin
  readln (f,v[i].x,v[i].y,v[i].cost);
 end;
 sort(1,m);
 for i:=1 to n do t[i]:=-1;
 suma:=0;  k:=0;
 for i:=1 to m do
 begin
  a:=tata(v[i].x);
  b1:=tata(v[i].y);
  if a<>b1 then
  begin
   suma:=suma+v[i].cost;
   inc(k);
   retine[k]:=i;
   t[b1]:=a;
  end;
 end;
 writeln (g,suma);
 writeln (g,k);
 for i:=1 to k do
  writeln (g,v[retine[i]].x,' ',v[retine[i]].y);
  close (F); close (G);
end.