from heapq import heappop,heappush
h,w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(h-2)]

inf = 10**10
dist = [[inf]*w for i in range(h-2)]

H = []
for i in range(h-2):
    if A[i][0] != -1:
        dist[i][0] = A[i][0]
        heappush(H,[A[i][0],i,0])


while H:
    dis,x,y = heappop(H)
    if dist[x][y] != dis:
        continue

    for dx in range(-1,2):
        for dy in range(-1,2):
            if dx == 0 and dy == 0:
                continue
            nx = x+dx
            ny = y+dy
            if 0 <= nx < h-2 and 0 <= ny < w and A[nx][ny] != -1:
                nd = dis + A[nx][ny]
                if nd < dist[nx][ny]:
                    dist[nx][ny] = nd
                    heappush(H,[nd,nx,ny])


ans = inf
for i in range(h-2):
    ans = min(ans,dist[i][-1])
if ans == inf:
    ans = -1
print(ans)