Program dijkstra;
type lista = ^celula;
     celula = record
                    nod : longint;
                    cost : longint;
                    pred : lista;
               end;
     sol= record
                 x,y : longint;
          end;
const INF=200000000;
var Lda : array [1..200005] of lista;
    r  :lista;
    H,D,viz,source,poz: array [1..200005] of longint;
    Solutie:array[1..200000] of sol;
    n,i,a,b,c,v,k,p,lungime,aux,s,f: longint;
    b1,b2 : array[0..1 shl 17] of char;

procedure coboara(k : longint);
  var fiu,aux : longint;
    begin
         repeat
               fiu:=0;
               if k*2<=lungime then
                  begin
                       fiu:=k*2;
                       if  (k*2<lungime) then
                           if (D[H[k*2+1]]<D[H[k*2]]) then fiu:=k*2+1;
                       if D[H[fiu]]>=D[H[k]] then fiu:=0
                  end;
                  if fiu<>0 then begin
                                       aux:=H[k];
                                       H[k]:=H[fiu];
                                       H[fiu]:=aux;
                                       aux:=poz[H[k]];
                                       poz[H[k]]:=poz[H[fiu]];
                                       poz[H[fiu]]:=aux;
                                       k:=fiu;
                                 end;

         until fiu=0;
   end;

begin
   assign(input,'apm.in'); settextbuf(input,b1); reset(input);
   assign(output,'apm.out'); settextbuf(output,b2); rewrite(output);
   readln(n,p);
   for i:=1 to p do begin
                        readln(a,b,c);
                        new(r);
                        r^.nod:=b;
                        r^.cost:=c;
                        r^.pred:=lda[a];
                        lda[a]:=r;
                        new(r);
                        r^.nod:=a;
                        r^.cost:=c;
                        r^.pred:=lda[b];
                        lda[b]:=r;
                    end;

   for i:=2 to n do D[i]:=INF;
   D[1]:=0;
   H[1]:=1;
   lungime:=1;
   viz[1]:=1;
   poz[1]:=1;
   while lungime>0 do begin
                          for i:=lungime div 2 downto 1 do coboara(i);
                          v:=H[1];
                          f:=f+1;
                          solutie[f].x:=v;
                          solutie[f].y:=source[H[1]];
                          s:=s+D[v];
                          r:=lda[v];
                          H[1]:=H[lungime];
                          poz[H[1]]:=poz[H[lungime]];
                          lungime:=lungime-1;
                          coboara(1);
   while r<>nil do begin
                        if viz[r^.nod]=0 then begin
                                                   lungime:=lungime+1;
                                                   H[lungime]:=r^.nod;
                                                   viz[r^.nod]:=1;
                                                   poz[r^.nod]:=lungime;
                                              end;
                        if r^.cost<D[r^.nod] then begin
                                                        D[r^.nod]:=r^.cost;
                                                        source[r^.nod]:=v;
                                                  end;
                    {    k:=poz[r^.nod];

             while (k>1) and (D[k]<D[k div 2]) do begin
                                                      aux:=H[k];
                                                      H[k]:=H[k div 2];
                                                      H[k div 2]:=aux;
                                                      aux:=poz[H[k]];
                                                      poz[H[k]]:=poz[H[k div 2]];
                                                      poz[H[k div 2]]:=aux;
                                                      k:=k div 2;
                                                  end; }

                                          r:=r^.pred;
                                                   end;
                                          end;


   writeln(s);
   writeln(f-1);
   for i:=2 to f do writeln(solutie[i].x,' ',solutie[i].y);
   close(input);
   close(output);
end.