const infile='apm.in';
  outfile='apm.out';
  maxn=200003;
  maxm=400003;
  infinit=maxlongint;
type nod=^pnod;
  pnod=record  inf:longint; cost:integer; next:nod; end;
  elem=record  no,c:longint; end;
var a:array[1..maxn]of nod;
  h:array[1..maxn]of elem;
  p,poz:array[1..maxn]of longint;
  n,vf,m,capm:longint;

 procedure citire;
 var i,j:longint;
   k:integer;
   q:nod;
 begin
   assign(input,infile); reset(input); readln(n,m);
   while(m>0)do begin
     readln(i,j,k); dec(m);
     new(q); q^.inf:=j; q^.cost:=k; q^.next:=a[i]; a[i]:=q;
     new(q); q^.inf:=i; q^.cost:=k; q^.next:=a[j]; a[j]:=q;
     end;
   close(input);
 end;

 procedure init;
 var i:longint;
 begin
   for i:=2 to n do begin h[i].no:=i; h[i].c:=infinit; poz[i]:=i; p[i]:=1;
     end;
   h[1].no:=1; h[1].c:=0; poz[1]:=1; p[1]:=0;
   vf:=n; capm:=0;
 end;

 procedure comb(i:longint);
 var v:elem;
   tata,fiu:longint;
 begin
   v:=h[i]; tata:=i; fiu:=i shl 1;
   while(fiu<=vf)do begin
     if(fiu<vf)and(h[fiu].c>h[fiu+1].c)then inc(fiu);
     if(v.c>h[fiu].c)then begin
       poz[h[fiu].no]:=tata; h[tata]:=h[fiu];
       tata:=fiu; fiu:=fiu shl 1;
       end
     else fiu:=vf+1;
     end;
   poz[v.no]:=tata; h[tata]:=v;
 end;

 procedure insert(i:longint);
 var v:elem;
   tata,fiu:longint;
 begin
   v:=h[i]; fiu:=i; tata:=i shr 1;
   while(tata<>0)and(h[tata].c>v.c)do begin
     poz[h[tata].no]:=fiu; h[fiu]:=h[tata];
     fiu:=tata; tata:=fiu shr 1;
     end;
   poz[v.no]:=fiu; h[fiu]:=v;
 end;

 function exmin:longint;
 begin
   exmin:=h[1].no; poz[h[1].no]:=0; inc(capm,h[1].c);
   h[1]:=h[vf]; dec(vf); comb(1);
 end;

 procedure prim;
 var q:nod;
   min:longint;
 begin
   init;
   while(vf>0)do begin
     min:=exmin;
     q:=a[min];
     while(q<>nil)do begin
       if(poz[q^.inf]>0)then
         if(h[poz[q^.inf]].c>q^.cost)then begin
           h[poz[q^.inf]].c:=q^.cost; p[q^.inf]:=min; insert(poz[q^.inf]);
           end;
       q:=q^.next;
       end;
     end;
 end;

 procedure afisare;
 var i:longint;
 begin
   assign(output,outfile); rewrite(output); writeln(capm); writeln(n-1);
   for i:=2 to n do writeln(p[i],' ',i);
   close(output);
 end;

begin
citire; prim; afisare;
end.