program prim_n2;
const inf=1 shl 30;
 type lista=^celula;
        celula=record
             info,cost:longint;
             pred:lista;
             end;
        var a:array[0..200000] of lista;
        used,d,p,sol,h:array[0..200000] of longint;
        n,m,x,y,z,i,j,k,min,nr,sum,size_h,poz:longint;
        r:lista;
        bufin,bufout:array[1..1 shl 17] of char;


 procedure heapdown(k:longint);
  var s,aux:longint;
 begin
  repeat
    s:=0;
    if 2*k<=size_h then s:=2*k;
    if (2*k+1<=size_h)and (d[h[2*k+1]]<d[h[2*k]]) then s:=2*k+1;
    if d[h[k]]<d[h[s]] then s:=0;

    if s<>0 then
      begin
        aux:=h[k];
        h[k]:=h[s];
        h[s]:=aux;
        k:=s;
      end;
  until s=0;
 end;

 procedure heapup(k:longint);
  var aux:longint;
 begin
   aux:=h[k];
   while (k>1)and (d[h[k]]<d[h[k div 2]]) do
     begin
       h[k]:=h[k div 2];
       k:=k div 2;
     end;
   h[k]:=aux;
 end;




 begin
  assign(input,'apm.in');
  reset(input);assign(output,'apm.out');
  rewrite(output);
  settextbuf(input,bufin);
  settextbuf(output,bufout);

  readln(n,m);

  for i:=1 to m do begin
    readln(x,y,z);
    new(r); r^.info:=y; r^.cost:=z; r^.pred:=a[x]; a[x]:=r;
    new(r); r^.info:=x; r^.cost:=z; r^.pred:=a[y]; a[y]:=r;
    end;

  for i:=1 to n do d[i]:=inf;
  d[1]:=0;
  for i:=1 to n do h[i]:=i;
  size_h:=n;

  p[1]:=-1;

  for i:=1 to n do begin
           k:=h[1];
           h[1]:=h[size_h];
           dec(size_h);
           heapdown(1);


           if p[k]<>-1 then
             begin
               inc(nr); sol[nr]:=k;
               sum:=sum+d[k];
             end;
           r:=a[k];
           while r<>nil do
            begin
              poz:=0;
              for j:=1 to size_h do
                if h[j]=r^.info then begin poz:=j; break; end;
              if poz<>0 then
                  if d[r^.info]>r^.cost then begin
                                d[r^.info]:=r^.cost;
                                p[r^.info]:=k;
                                heapup(poz);
                                end;
             r:=r^.pred;
             end;
           end;
  writeln(sum);
  writeln(n-1);
  for i:=1 to n-1 do
    writeln(sol[i],' ',p[sol[i]]);
  close(output);
 end.