program krushkal;
type natural=record
 x,y,c:longint;
end;
var f,g:text;
    v:array[1..400000] of natural;
    nr,t:array[1..400000] of longint;
    n,m,i,mijloc,a,b,suma,k:longint;
    ba:array[1..400000] of natural;

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


procedure sortare (st,dr:longint);
 var    aux:natural;
        mijloc:longint;
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;
  sortare (st,mijloc);
  sortare (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
  readln (f,v[i].x,v[i].y,v[i].c);
  sortare(1,m);
 for i:=1 to n 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[a]:=t[a]+t[b];  }
   t[b]:=a;
   suma:=suma+v[i].c;
   k:=k+1;
   nr[k]:=i;
  end;
 end;
 writeln (g,suma);
 writeln (g,k);
 for i:=1 to k do
  writeln (g,v[nr[i]].x,' ',v[nr[i]].y);
 close (f);
 close (G);
end.