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:array[1..200005] of mi;
    t,nr:array[1..200005] of longint;
function tata(nod:longint):longint;
  begin
    while t[nod]<> nod do
       t[nod]:=nod;
       tata:=nod;
  end;
{procedure sort;
begin
  repeat
  ok:=true;
    for i:=1 to  m-1 do
      if v[i].c>v[i+1].c then
        begin
        aux:=v[i];
        v[i]:=v[i+1];
        v[i+1]:=aux;
        ok:=false;
        end;
  until ok; }
procedure merge(m,st,sf:longint);
var i,j,k:longint;
b:array[1..200005] of mi;
  begin
    i:=st;
    j:=m+1;
    k:=1;
      while (i<=m) and (j<=sf) do
        begin
          if v[i].c<v[j].c then
            begin
            b[k]:=v[i];
            i:=i+1;
            end
            else
            begin
            b[k]:=v[j];
            j:=j+1;
            end;
          k:=k+1;
        end;
      if i<=m then
        begin
          for j:=i to m do
             begin
             b[k]:=v[j]; k:=k+1;
             end;
        end
        else
          for i:=j to sf do
            begin
            b[k]:=v[i];
            k:=k+1;
            end;
        k:=1;
          for i:=st to sf do
            begin
            v[i]:=b[k];
            k:=k+1;
            end;
  end;
procedure sort(st,sf:longint);
var aux:mi;
m:longint;
begin
   if (sf-st)<=1 then
     begin
       if v[st].c>v[sf].c then
          begin
          aux:=v[st]; v[st]:=v[sf]; v[sf]:=aux;
          end;
     end
     else
       begin
         m:=(st+sf) div 2;
         sort(st,m);
         sort(m+1,sf);
         merge(m,st,sf);
       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;
    sort(1,m);

      k:=0;
      for i:=1 to n do
         begin
         t[i]:=i;
         end;

    for i:=1 to m do
      begin
        a:=tata(v[i].x);
        b:=tata(v[i].y);
          if a<>b then
            begin
           {  t[a]:=t[a]+t[b];  }
              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.