const max=101;
      max2=501;
var n,m,i,j,len:longint;
    a:array[1..max,1..max2]of extended;
    b:array[1..max,1..max2]of longint;
    d:array[1..max2]of extended;
    min:extended;

function done(l,r:longint):extended;
var i:longint;
    sum,mint:extended;
begin
     mint:=a[l,r]+a[l+1,r];
     b[l,r]:=r;
     sum:=0;
     for i:=r downto 1 do begin
         sum:=sum+a[l,i];
         sum:=sum+a[l+1,i];
         if sum<mint then begin mint:=sum;
                                b[l,r]:=i;
                                end;
         sum:=sum-a[l+1,i];
         end;
         sum:=0;
         for i:=r to m do begin
         sum:=sum+a[l,i];
         sum:=sum+a[l+1,i];
         if sum<mint then begin mint:=sum;
                                b[l,r]:=i;
                                end;
         sum:=sum-a[l+1,i];
         end;
     done:=mint;
end;
procedure output(han:longint);
var i,k,h:longint;
    c:array[1..max*max2]of longint;
begin
     h:=1;
     fillchar(c,sizeof(c),0);
     k:=0;
     while h<=n do begin
           if b[h,han]>han then
           for i:=han to b[h,han] do begin
           inc(k);
           c[k]:=i;
           end
           else for i:=han downto b[h,han] do begin
                inc(k);
                c[k]:=i;
                end;
           han:=b[h,han];
           inc(h);
           end;
     for i:=1 to k do writeln(c[i]);
end;
begin
     read(n);
     read(m);
     for i:=1 to n do
         for j:=1 to m do
             read(a[i,j]);
     for i:=n downto 1 do begin
         for j:=1 to m do d[j]:=done(i,j);
         for j:=1 to m do a[i,j]:=d[j];
         end;
    min:=a[1,1];len:=1;
    for i:=2 to m do
        if min>a[1,i] then begin min:=a[1,i];len:=i;end;
    output(len);
end.

I solved this problem using dijkstra for each floor, it works O(M*N^2).
Try to use {$Q-,R-,S-,I-}