program ind;
var f,g:Text;
    s,ln,col:Array [1..20000] of integer;
    c:array [1..2000,1..2000] of integer;
    min,n,i,j,k,m,cc,ii,cont,p:integer;
procedure citire;
begin
    assign (f,'apm.in'); reset (f);
    assign (g,'apm.out') ; rewrite (g);
    readln (f,n,m);
    for i:=1 to n do
       for j:=1 to n do
          c[i,j]:=maxint;
    for i:=1 to m do
        begin
             readln (f,ii,j,cc);
             c[ii,j]:=cc;
             c[j,ii]:=cc;
        end;
    close (f);
end;
begin
     citire;
     cont:=0;
     for i:=2 to n do
          s[i] :=1;
     for k:=1 to n-1 do
         begin
            min:=maxint;
            for i:=1 to n do
                if s[i]<>0 then
                      if min>c[s[i],i] then
                          begin
                               min:=c[s[i],i] ;
                               j:=i;
                          end;
                      cont:=cont+c[j,s[j]] ;
                      p:=p+1;
                      ln[p]:=j;
                      col[p]:=s[j];
            for i:=1 to n do
                if (s[i]=1) and(c[i,s[i]]>c[i,j])  then
                     s[i]:=j;
                s[j]:=0;
         end;
     writeln (g,cont);
     writeln (g,p);
     for i:=1 to p do
         writeln (g,ln[i],' ',col[i]) ;
     close (g);
end.