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

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