program a1029;
const
     maxm=3;
     maxn=4;
var
   a:array[1..maxm,1..maxn]of longint;
   cost:array[1..maxm,1..maxn,1..2]of longint;
   m,n,i,j,k,max,mn,min,xn,wn,s1:longint;
   wa:array[1..2*maxm]of longint;
function sum(x,y,i:integer):longint;
         var
         j:integer;
         s:longint;
         begin
              s:=0;
              if x<y then
                 for j:=x to y do if s>1000000000 then begin
                     s:=1000000000;
                     break;
                 end else s:=s+a[i,j]
              else
                  for j:=x downto y do if s>1000000000 then begin
                      s:=1000000000;
                      break;
                  end else s:=s+a[i,j];
              sum:=s;
         end;
procedure print(x,y:longint);
          var
          i:longint;
          begin
               if x<y then
                  for i:=x to y do writeln(i)
               else
                   for i:=x downto y do writeln(i);
          end;
begin
     fillchar(a,sizeof(a),0);
     fillchar(cost,sizeof(cost),0);
     readln(m,n);
     for i:=1 to m do
         for j:=1 to n do read(a[i,j]);
     for i:=2 to m do
         for j:=1 to n do cost[i,j,1]:=1000000000;
     for i:=1 to n do cost[1,i,1]:=a[1,i];
     for i:=2 to m do
         for j:=1 to n do begin
             max:=maxlongint;
             mn:=0;
             for k:=1 to n do begin
                 s1:=sum(j,k,i);
                 if s1+cost[i-1,k,1]<max then begin
                    max:=s1+cost[i-1,k,1];
                    mn:=k;
                 end;
             end;
             cost[i,j,1]:=max;
             cost[i,j,2]:=mn;
         end;
     min:=maxlongint;
     mn:=0;
     xn:=0;
     wn:=0;
     for i:=1 to n do if cost[m,i,1]<min then begin
         min:=cost[m,i,1];
         mn:=cost[m,i,2];
         xn:=i;
     end;
     inc(wn);
     wa[wn]:=xn;
     while mn<>0 do begin
           inc(wn);
           wa[wn]:=mn;
           mn:=cost[m-1,mn,2];
           dec(m);
     end;
     writeln(wa[wn]);
     for i:=wn-1 downto 1 do print(wa[i+1],wa[i]);
end.