{Jugariu Mihai}
{2009 XI-XII Cerc}
var lun,a,b,c,d,h:array[1..400000]of longint;
    da:array[1..400015]of boolean;
    bufin,bufout:array[1..1200000]of byte;
    s:int64;
    x,y,i,j,n,m,nr:longint;
    ok:boolean;
    f,g:text;

procedure ordon(i,j:longint);
  var k,l,p,mij:longint;
 begin;
  if i=j then
         else
   begin;
    mij:=(i+j)div 2;
    ordon(i,mij);
    ordon(mij+1,j);
    k:=i;p:=mij+1;l:=i-1;
    repeat
     if lun[k]<lun[p] then
      begin;
       inc(l);
       h[l]:=lun[k];
       c[l]:=a[k];
       d[l]:=b[k];
       inc(k);
      end
                  else
      begin;
       inc(l);
       h[l]:=lun[p];
       c[l]:=a[p];
       d[l]:=b[p];
       inc(p);
      end;
    until(p>j)or(k>mij);
    if k>mij then
     for k:=p to j do
      begin;
       inc(l);
       h[l]:=lun[k];
       c[l]:=a[k];
       d[l]:=b[k];
      end
             else
     for p:=k to mij do
      begin;
       inc(l);
       h[l]:=lun[p];
       c[l]:=a[p];
       d[l]:=b[p];
      end;
    for k:=i to j do lun[k]:=h[k];
    for k:=i to j do a[k]:=c[k];
    for k:=i to j do b[k]:=d[k];
   end;
 end;

function min(i,j:longint):longint;
 begin;
  if i>j then min:=j
         else min:=i;
 end;

begin;
assign(f,'apm.in');
reset(f);
assign(g,'apm.out');
rewrite(g);
settextbuf(f,bufin);
settextbuf(g,bufout);
read(f,n,m);
for i:=1 to m do
 read(f,a[i],b[i],lun[i]);

ordon(1,m);
for i:=1 to m do h[i]:=0;
for i:=1 to m do da[i]:=false;
s:=0;
nr:=0;
for i:=1 to m do
 if h[a[i]]=0 then
  begin;
   if h[b[i]]<>0 then
    begin;
     inc(nr);
     s:=s+lun[i];
     h[a[i]]:=h[b[i]];
     da[i]:=true;
    end
                else
    begin;
     inc(nr);
     s:=s+lun[i];
     h[a[i]]:=min(a[i],b[i]);
     h[b[i]]:=min(a[i],b[i]);
     da[i]:=true;
    end;
  end
              else
  begin;
   if h[b[i]]=0 then
    begin;
     inc(nr);
     s:=s+lun[i];
     h[b[i]]:=h[a[i]];
     da[i]:=true;
    end
                else
    begin;
     if h[a[i]]<>h[b[i]] then
      begin;
       inc(nr);
       s:=s+lun[i];
       x:=h[a[i]];
       y:=h[b[i]];
       da[i]:=true;
       for j:=1 to n do
        if(h[j]=x)or(h[j]=y)then
         h[j]:=min(x,y);
      end;
    end;
  end;
write(g,s);
writeln(g);
write(g,nr);
for i:=1 to m do
 if da[i] then
  begin;
   writeln(g);
   write(g,a[i],' ',b[i]);
  end;
close(g);
close(f);
end.