uses crt;
type
 op=record
  a,b,c:integer;
  end;
 kl=array[1..400000] of op;
 lk=array[1..200000]of integer;
var
 a,b,c,d,i,j,m,n,s,h:integer;
 f,g:text;
 v:kl;
 d2:op;
 p,p1,p2:lk;
procedure quik(a,b:integer);
var k,i,j:integer;
begin
   i:=a;j:=b;
   k:=v[(a+b)div 2].c;
   while i<=j do
     begin
       while (v[i].c<k) do
         inc(i);
       while (v[j].c>k) do
         dec(j);
       if i<=j then begin
        d2:=v[i];
        v[i]:=v[j];
        v[j]:=d2;
        inc(i);
        dec(j);          end;
     end;
  if i<b then quik(i,b);
  if j>a then quik(a,j);
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].a,v[i].b,v[i].c);
    p[i]:=i;
  end;
 quik(1,m);
 h:=1; i:=1;s:=0;
 while h<>n do
  begin
   a:=p[v[i].a];
   b:=p[v[i].b];
   if a<>b
    then
     begin
      inc(h);         s:=s+v[i].c;
      p1[h-1]:=v[i].a;
      p2[h-1]:=v[i].b;
      for j:=1 to n do
       if p[j]=a then p[j]:=b;
     end;
    inc(i);
  end;
  writeln(g,s);
  writeln(g,h-1);
  for i:=1 to h-1 do
   begin
    writeln(g,p1[i],' ',p2[i]);
   end;
{ for i:=1 to m do
  writeln(g,v[i].a,v[i].b,v[i].c);  }
 close(f);
 close(g);
end.