Program p1;
var b1,b2:array[1..1 shl 20] of char;
    i,n,m,s,k,x,y,aux:longint;  fi,fo:text;
    tata,rang,a,b,d:array[0..200001] of longint;
    c:array[0..400005] of -1001..1001;

Function radacina(x:longint):longint;
begin
    while tata[x]<>x do x:=tata[x];
    radacina:=x;
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;

Procedure quick(left,right:longint);
var mijl,i,j:longint;
begin
    mijl:=c[(left+right) div 2];
    i:=left; j:=right;
    while i<j do begin
                 while c[i]<mijl do i:=i+1;
                 while c[j]>mijl do j:=j-1;
                 if i<=j then begin
                              aux:=a[i]; a[i]:=a[j]; a[j]:=aux;
                              aux:=b[i]; b[i]:=b[j]; b[j]:=aux;
                              aux:=c[i]; c[i]:=c[j]; c[j]:=aux;
                              i:=i+1; j:=j-1;
                              end;
                 end;
    if i<right then quick(i,right);
    if left<j then quick(left,j);
end;

begin
    assign(fi,'apm.in'); reset(fi);
    assign(fo,'apm.out'); rewrite(fo);
    settextbuf(fi,b1); settextbuf(fo,b2);
    readln(fi,n,m); k:=0; s:=0;
    for i:=1 to n do begin tata[i]:=i; rang[i]:=1; end;
    for i:=1 to m do readln(fi,a[i],b[i],c[i]);

    quick(1,m);
    for i:=1 to m do  begin
                      x:=radacina(a[i]);
                      y:=radacina(b[i]);
                      if (x<>y) then begin
                                     uneste(x,y);
                                     k:=k+1;
                                     d[k]:=i;
                                     s:=s+c[i];
                                     end;
                      end;
    writeln(fo,s); writeln(fo,k);
    for i:=1 to k do writeln(fo,a[d[i]],' ',b[d[i]]);
    close(fi); close(fo);
end.