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:array[0..200001] of 0..200003;
    a,b,d:array[0..400005] of 0..200003;
    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 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 m do begin
                      readln(fi,a[i],b[i],c[i]);
                      tata[i]:=i;
                      rang[i]:=1;
                      end;
    quick(1,m);
    for i:=1 to m do  begin
        x:=radacina(a[i]);
        y:=radacina(b[i]);
       if (x<>y) then begin
                      if rang[x]>rang[y] then tata[y]:=x else tata[x]:=y;
                      s:=s+c[i];
                      k:=k+1;
                      d[k]:=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.