program p1;
var a,b,c,d,tata,rang:array[0..200001] of longint;
    b1,b2:array[0..1 shl 21] of char;
    f,g:text;
    i,n,j,k,m,u,x,y,s:longint;

procedure swap (var x,y:longint);
var aux:longint;
begin
 aux:=x;
 x:=y;
 y:=aux;
end;



procedure quick(left,right:longint);
var mijl,i,j:longint;
begin
 i:=left;
 j:=right;
 mijl:=c[(i+j) div 2];
  while i<j do begin
                while c[i]<mijl do inc(I);
                while c[j]>mijl do dec(J);
                if i<=j then begin
                             swap(a[i],a[j]);
                             swap(b[i],b[j]);
                             swap(c[i],c[j]);
                             inc(I);
                             dec(J);
                             end;
                end;
 if i<right then quick (i,right);
 if left<j then quick (left,j);
end;


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;


begin
assign(f,'apm.in');reset(F);
assign(g,'apm.out');rewrite(G);
settextbuf(f,b1);
settextbuf(g,b2);
readln(f,n,m);
 for i:=1 to n do begin
                tata[i]:=i;
                rang[i]:=1;
                  end;
 for i:=1 to m do readln(f,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

                        inc(K);
                        d[k]:=i;
                        s:=s+c[i];

                        uneste(x,y);
                             end;
                  end;
 writeln(g,s);
 writeln(G,k);
 for i:=1 to k do writeln(g,a[d[i]],' ',b[d[i]]);
close(F);
close(G);
end.