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;  dd:rec;
procedure quick(a,b:longint);
  var k,i,j:longint;
  begin
     i:=a;j:=b;
     k:=v[(a+b)div 2].c;
     while i<=j do begin
       while v[i].c<k do inc(i);
       while v[j].c>k do dec(j);
       if i<=j then begin
         dd:=v[i];
         v[i]:=v[j];
         v[j]:=dd;
         inc(i); dec(j); end;
         end;
     if i<b then quick(i,b);
     if j>a then quick(a,j);     {copyrigt}
  end;
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;
  quick(1,m); c:=0; k:=0;
  repeat
  inc(k);
  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[k].c;
  end;
  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,' ');
    writeln(f,v[q[i]].b);
    end;
  close(f);
end.