type cell=record
     x,y,val:longint;
     end;

var a,b:array[0..400001] of cell;
    i,j,k,l,n,m,t:longint;
    c:cell;
    d,e:array[1..400001] of longint;
    f,g:text;

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

procedure merge(k,k1:longint);
var i,j,l,v1,v:longint;
begin
if k>k1 then
  begin
  l:=k;
  k:=k1;
  k1:=l;
  end;
if (d[k]=d[k1]) then
   begin
   d[k]:=k;
   d[k1]:=k;
   end
                else
   if (d[k]=0) and (d[k1]<>0) then
     begin
     d[k]:=d[k1];
     end
                              else
     if (d[k]<>0) and (d[k1]=0) then
     begin
     d[k1]:=d[k];
     end
                              else
     begin
     v:=d[k];
     v1:=d[k1];
     if d[k1]<d[k] then l:=d[k1]
                   else l:=d[k];
     for i:=1 to m do
       if (d[i]=v) or (d[i]=v1) then d[i]:=l;
     end;
end;

begin
assign(f,'apm.in');
reset(f);
assign(g,'apm.out');
rewrite(g);
read(f,n,m);
for i:=1 to m do
  read(f,a[i].x,a[i].y,a[i].val);
{ordonare}
{repeat
  k:=1;
  for i:=1 to m-1 do
    if a[i].val>a[i+1].val then
      begin
      c:=a[i];
      a[i]:=a[i+1];
      a[i+1]:=c;
      k:=0;
      end;
until k=1; }
ordon(1,m);
for i:=1 to n do
  begin
  d[i]:=0;
  e[i]:=0;
  end;
l:=0;
t:=0;
for i:=1 to m do
  begin
  if (d[a[i].x]<>d[a[i].y]) or (d[a[i].x]=0) then
    begin
    inc(l);
    e[i]:=1;
    merge(a[i].x,a[i].y);
    t:=t+a[i].val;
    end;
  end;
writeln(g,t);
writeln(g,l);
for i:=1 to m do
  if e[i]=1 then writeln(g,a[i].x,' ',a[i].y);
close(f);
close(g);
end.