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

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

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