program urgenta;
type    elem=record
        x,y,c:longint;
end;
        vect=array[1..400000] of elem;
        vector=array[1..200000] of longint;
var     aux,v:vect;
        tata,nr:vector;
        gr,a,b,s,k,i,j,p,n,m,l:longint;
        f,g:text;

procedure interclasare(st,dr,mij:longint);
var       i,j,k:longint;
begin
  i:=st; j:=mij+1; k:=0;
  while (i<=mij) and (j<=dr) do
      if v[i].c<v[j].c then
        begin
          inc(k);
          aux[k]:=v[i];
          inc(i);
        end
      else
        begin
          inc(k);
          aux[k]:=v[j];
          inc(j);
        end;
  if j<=dr then
     for i:=j to dr do
       begin
         inc(k);
         aux[k]:=v[i];
       end;
  if i<=mij then
    for j:=i to mij do
      begin
        inc(k);
        aux[k]:=v[j];
      end;
  k:=0;
  for i:=st to dr do
    begin
      inc(k);
      v[i]:=aux[k];
    end;

end;

procedure sort(st,dr:longint);
var       mij:longint;
          u:elem;
begin
  if dr-st<=1 then
    begin
      if v[st].c>v[dr].c then
        begin
          u:=v[st];
          v[st]:=v[dr];
          v[dr]:=u;
        end;
    end
  else
    begin
      mij:=(st+dr) div 2;
      sort(st,mij);
      sort(mij+1,dr);
      interclasare(st,dr,mij);
    end;
end;

function radacina(nod:longint):longint;
begin
  if tata[nod]<0 then radacina:=nod
    else
      begin
        tata[nod]:=radacina(tata[nod]);
        radacina:=tata[nod];
      end;
end;


begin
  assign(f,'apm.in');
  reset(f);
  assign(g,'apm.out');
  rewrite(g);
  readln(f,n,m);
  for i:=1 to m do
      readln(f,v[i].x,v[i].y,v[i].c);
  sort(1,m);
  k:=0;
  for i:=1 to n do
     tata[i]:=-1;
  for i:=1 to m do
    begin
            a:=radacina(v[i].x);
            b:=radacina(v[i].y);
            if a<>b then
              begin
                tata[b]:=a;
                k:=k+1;
                nr[k]:=i;
                s:=s+v[i].c;
              end;
    end;
  writeln(g,s);
  writeln(g,k);
  for i:=1 to k do
    begin
      writeln(g,v[nr[i]].x,' ',v[nr[i]].y);
    end;
  close(f);
  close(g);
end.