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:array[0..200000] of longint;
        n,m,x,y,z,i,j,k,min,nr,sum:longint;
        r:lista;

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

  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;
  p[1]:=-1;

  for i:=1 to n do begin
           k:=1;
           min:=inf;
           for j:=1 to n do
            if (used[j]=0) and (d[j]<min)then begin
                 min:=d[j];
                 k:=j;
                 end;
           if p[k]<>-1 then
             begin
               inc(nr); sol[nr]:=k;
               sum:=sum+d[k];
             end;
           used[k]:=1;
           r:=a[k];
           while r<>nil do
            begin
            if used[r^.info]=0 then
             if d[r^.info]>r^.cost then begin
                                d[r^.info]:=r^.cost;
                                p[r^.info]:=k;
                                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.