program apm;
type element=record
x1,x2:integer;
end;
var f,g:text;
c:array[1..800,1..800] of integer;
c1,c2,c3,sum,nr,n,m,min,k,i,j,j2:integer;
s:array[1..800]of integer;
w:array[1..800] of element;
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;
       c[c2,c1]:=c3;
     end;
     for i:=1 to n do
       for j:=1 to n  do
         if c[i,j]=0 then c[i,j]:=maxint;

     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+c[j,s[j]];
               nr:=nr+1;
               w[nr].x1:=s[j];
               w[nr].x2:=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,sum);
       writeln(g,nr);
       for i:=1 to nr do
         writeln(g,w[i].x1,' ',w[i].x2);
  close(f); close(g);
end.