Program Kruscal;
 type tip=record
       x,y,t:longint;
       end;
var a,b:array [1..4000] of tip;
    lr,gr,sol1,sol2:array [1..2000] of longint;
    aux:array [-1001..1000] of longint;
    b1,b2:array [1..1 shl 17] of char;
    i,j,n,m,ct,k,v,w:longint;
    fi,fo:text;
function grupa(i:longint):longint;
 begin
  if lr[i]=gr[i] then grupa:=i
                  else grupa:=grupa(lr[gr[i]]);
end;
begin
 assign(fi,'apm.in');
  assign(fo,'apm.out');
 settextbuf(fi,b1); settextbuf(fo,b2);
 reset(fi); rewrite(fo);
 readln(fi,n,m);
 for i:=1 to n do begin lr[i]:=i; gr[i]:=i; end;
  for i:=1 to m do begin readln(fi,a[i].x,a[i].y,a[i].t); inc(aux[a[i].t]); end;
    for i:=-1000 to 1000 do aux[i]:=aux[i-1]+aux[i];
 for i:=1 to m do begin
                   b[aux[a[i].t]]:=a[i];
                    dec(aux[a[i].t]);
                   end;
  i:=1;
   while k<n-1 do begin
   v:=grupa(b[i].x); w:=grupa(b[i].y);
     if v<>w then begin
                   inc(k);
                    ct:=ct+b[i].t;
                      sol1[k]:=b[i].x; sol2[k]:=b[i].y;
                                  {  v:=l[b[i].y]; w:=l[b[i].x];
                                   for j:=1 to n do
                                    if l[j]=v then l[j]:=w; }
                    gr[w]:=v;
                                   end;
                     inc(i);
     end;
  writeln(fo,ct); writeln(fo,n-1);
 for i:=1 to n-1 do writeln(fo,sol2[i],' ',sol1[i]);
 close(fo);
end.