{APM(Arbori partiali de cost minim) }


program apm;
type mi=record
     x,y,c:longint;
     end;
var f,g:text;
    n,m,i,j,s,a,b,k:longint;
    ok:boolean;
    aux:mi;
    v,b1:array[1..200005] of mi;
    t,nr:array[1..200005] of longint;


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

procedure combheap(i,n:integer);
var x:mi;
    tat,fiu:integer;
begin
    x:=v[i];
    tat:=i;
    fiu:=2*i;
    while fiu<=n do
      begin
          if fiu<n then
            if v[fiu].c<v[fiu+1].c then
               fiu:=fiu+1;

            if x.c<v[fiu].c then
              begin
                  v[tat]:=v[fiu];
                  tat:=fiu;
                  fiu:=fiu*2;
              end
           else
              fiu:=n+1;
      end;
      v[tat]:=x;
end;

procedure creareheap;
begin
    for i:=n div 2 downto 1 do
      begin
          combheap(i,n);
      end;
end;

procedure heapsort;
var aux:mi;

begin
    creareheap;
    for i:=n downto 2 do
      begin
          aux:=v[1];  v[1]:=v[i]; v[i]:=aux;
          combheap(1,i-1);
      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
      begin
         readln(f,v[i].x,v[i].y,v[i].c);
      end;
  heapsort;

  k:=0;
  for i:=1 to m do
      t[i]:=-1;
  for i:=1 to m do
      begin
        a:=tata(v[i].x);
        b:=tata(v[i].y);
        if a<>b then
            begin
              t[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
      writeln(g,v[nr[i]].y,' ',v[nr[i]].x);
  close(f);
  close(g);
end.