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

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;
end;

Procedure swap3(i,j:longint);
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;
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
                              swap3(i,j);
                              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(input,'apm.in'); reset(input);
    assign(output,'apm.out'); rewrite(output);
    settextbuf(input,b1); settextbuf(output,b2);
    readln(n,m); k:=0; s:=0;
    for i:=1 to m do begin
                      readln(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
                      uneste(x,y);
                      s:=s+c[i];
                      k:=k+1;
                      d[k]:=i;
                      end;
                      end;
    writeln(s);
    writeln(k);
    for i:=1 to k do writeln(a[d[i]],' ',b[d[i]]);
    close(input); close(output);
end.