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

procedure interclasare (st,dr,mijloc:longint);
var i,j:longint;
    nr,k:longint;

begin
 i:=st; j:=mijloc+1; nr:=0;
 while (i<=mijloc) and (j<=dr) do
  if v[i].cost<v[j].cost then
  begin
   inc(nr); aux[nr]:=v[i]; inc(I);
  end
  else
  begin
   inc(nr); aux[nr]:=v[j]; inc(j);
  end;
 if i<=mijloc then
 begin
  for k:=i to mijloc do
  begin
   inc(nr); aux[nr]:=v[k];
  end;
 end;
 if j<=dr then
 begin
  for k:=j to dr do
  begin
   inc(nr); aux[nr]:=v[k];
  end;
 end;
 nr:=0;
 for i:=st to dr do
 begin
  inc(nr); v[i]:=aux[nr];
 end;
end;

procedure sortare (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;
  sortare(st,mijloc);
  sortare(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
  read (f,v[i].x,v[i].y,v[i].cost);
 for i:=1 to n do t[i]:=-1;
 sortare(1,m);
 s:=0;            nr:=0;
 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;
   s:=s+v[i].cost;
   inc(nr);
   retine[nr]:=i;
  end;
 end;
 writeln (g,s);
 writeln (g,nr);
 for i:=1 to nr do
 begin
 writeln (g,v[retine[i]].x,' ',v[retine[i]].y);

 end;
  close (f); close (G);
end.