type much=record s, d, c:longint; end;

var mu:array [1..400000] of much;
    r: array [1..200000] of much;
    disj:array[1..200000] of longint;
    buf1, buf2:array [1.. 1 shl 17] of char;
    x, y, z, i, j, n, m, d1, d2, leg1, leg2, t:longint;
    s:int64;
    aux:much;
    ok:boolean;
    f, g:text;

procedure pmj2 (fx:longint);
  begin
  if disj[fx]<>0 then
    begin
    pmj2(disj[fx]);
    if ok then disj[fx]:=leg2;
    end
                 else
    begin
    if fx<>leg1 then begin ok:=true; leg2:=fx; end;
    end;
  end;

procedure pmj (fx:longint);
  begin
  if disj[fx]<>0 then pmj(disj[fx]) else
    begin
    leg1:=fx;
    pmj2(d2);
    end;

  if ok then disj[fx]:=leg2;
  end;

procedure qsort (st, dr:longint);
var s, d, m:longint;
  begin
  s:=st; d:=dr; m:=st+random(dr-st+1);

  aux:=mu[m]; mu[m]:=mu[st]; mu[st]:=aux;

  while s<d do
    begin
    while (s<d) and (mu[d].c>=aux.c) do dec (d);
    mu[s]:=mu[d];
    while (s<d) and (mu[s].c<=aux.c) do inc (s);
    mu[d]:=mu[s];
    end;
  mu[s]:=aux;

  if s-st>1 then qsort (st, s-1);
  if dr-s>1 then qsort (s+1, dr);
  end;


begin
randomize;
assign (f, 'apm.in'); settextbuf (f, buf1); reset (f);
assign (g, 'apm.out'); settextbuf (g, buf2); rewrite (g);

read (f, n, m);
for i := 1 to m do readln (f, mu[i].s, mu[i].d, mu[i].c);

qsort (1, m);


for i := 1 to m do
  begin
  x:=mu[i].s; y:=mu[i].d; z:=mu[i].c;
  d1:=x; d2:=y;

  ok:=false;
  pmj(d1);
  if ok then
    begin
    s:=s+mu[i].c;
    inc (t);
    r[t]:=mu[i];
    end;
  end;

writeln (g, s); writeln (g, t);
for i := 1 to t do writeln (g, r[i].s, ' ', r[i].d);

close (f); close (g);

end.