program apm;
var f,g:text;
c:array[1..100,1..100] of integer;
c1,c2,c3,sum,nr,n,m,min,k,i,j,j2:integer;
s,w:array[1..100]of integer;
begin
  assign(f,'apm.in'); reset(f);
  assign(g,'apm.out'); rewrite(g);
    readln(f,n,m); sum:=0; nr:=0;  j2:=0;
    for i:=1 to m do
     begin
       readln(f,c1,c2,c3);
       c[c1,c2]:=c3;
     end;
     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;
               sum:=sum+s[j];
               nr:=nr+1;
               inc(j2);
               w[j2]:=s[i];
             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,sum);
       writeln(g,nr);
       for i:=1 to n do
         writeln(g,w[i],' ',i);
  close(f); close(g);
end.