uses crt;
type
 mut=^elem;
 elem=record
  a:longint;
  k:mut;
 end;
 lep=record
  a,b,c:longint;
  end;
 kl=array[0..200001] of mut;
 op=array[0..400001] of lep;
 lp=array[0..200001] of longint;
var
 p:mut;
 a,b,c,i,m,n,k,h,s:integer;
 d:op;
 v:kl;
 j,x,y:lp;
 f,g:text;
procedure csinal(k,m:longint);
var a:longint;b:lep;
begin
  repeat
   a:=0;
   if 2*k<=m
    then
     begin
      a:=2*k;
      if (k*2+1<=m)and(d[a].c>d[k*2+1].c)
       then a:=k*2+1;
      if d[k].c<d[a].c then a:=0;
     end;
   if a<>0 then
      begin
       b:=d[a];
       d[a]:=d[k];
       d[k]:=b;
       k:=a;
      end;
  until a=0;
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,d[i].a,d[i].b,d[i].c);
 for i:=m div 2 downto 1 do
   csinal(i,m);
 for i:=1 to n do
  begin
   new(p);
   p^.a:=i;
   p^.k:=v[i];
   v[i]:=p;
   j[i]:=i;
  end;
 k:=0;s:=0;
 while k<>n-1 do
  begin
   if j[d[1].a]<>j[d[1].b]
    then
     begin
      a:=j[d[1].a];b:=j[d[1].b];
      p:=v[a];
      while  p<>nil do
        begin
         j[p^.a]:=b;
         v[a]:=p^.k;
         p^.k:=v[b];
         v[b]:=p;
         p:=v[a];
        end;
      s:=s+d[1].c;inc(k);
      x[k]:=d[1].a;
      y[k]:=d[1].b;
     end;
   d[1]:=d[m];
   dec(m);
   csinal(1,m);
  end;
 writeln(g,s);
 writeln(g,n-1);
 for i:=1 to n-1 do
   writeln(g,y[i],' ',x[i]);
 close(f);
 close(g);
end.