type rec=record
     a,b,c:longint;
     end;
     vek=array[1..400000] of rec;
     vak=array[1..200000] of longint;
var i,j,n,m,s,k,min,c,d:longint; f:text; v:vek; x,q:vak;
begin
  assign(f,'apm.in');
  reset(f);
  readln(f,n,m);
  for i:=1 to m do
    readln(f,v[i].a,v[i].b,v[i].c);
  close(f);
  c:=0;  s:=0;
  for i:=1 to n do
    x[i]:=i;
  repeat
  min:=100000;
  for i:=1 to m do
    if (v[i].c<min) and (v[i].a>0) then begin min:=v[i].c; k:=i; end;
    if x[v[k].a]<>x[v[k].b] then begin
  d:=x[v[k].b];
  for i:=1 to n do
   if x[i]=d then x[i]:=x[v[k].a];
  inc(c); q[c]:=k;  s:=s+v[q[c]].c;
  end;
  v[k].a:=v[k].a*(-1);
  until c=n-1;
  assign(f,'apm.out');
  rewrite(f);
  writeln(f,s);
  writeln(f,c);
  for i:=1 to c do  begin
    write(f,v[q[i]].a*(-1),' ');
    writeln(f,v[q[i]].b);
    end;
  close(f);
end.