Program Kruscal;
 type tip=record
       x,y,t:longint;
       end;
var a,b:array [1..400000] of tip;
    tata,rang,sol1,sol2:array [1..200000] 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 radacina(x:longint):longint;
 var r,aux:longint;
begin
 r:=x;
  while tata[r]<>r do r:=tata[r];
   radacina:=r;
  while tata[x]<>x do begin aux:=tata[x]; tata[x]:=r; x:=aux; end;
end;
procedure uneste(x,y:longint);
begin
 if rang[x]>rang[y] then tata[y]:=x else tata[x]:=y;
  if rang[x]=rang[y] then inc(rang[y]);
 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 tata[i]:=i; rang[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:=radacina(b[i].x); w:=radacina(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;
                    uneste(v,w);
                   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.