from collections import defaultdict, deque
from heapq import heappush, heappop


def neighbors8(r: int, c: int) -> list[tuple[int, int]]:
    res = []
    for dr in range(-1, 2):
        for dc in range(-1, 2):
            if abs(dr) + abs(dc) == 0: continue
            nr = r + dr
            nc = c + dc
            res.append((nr, nc))

    return res


INF = 1 << 60
H, W = map(int, input().split())
A = []
for i in range(H):
    if i == 0 or i == H-1:
        A.append([INF] * W)
    else:
        A.append(list(map(int, input().split())))

starts = []
goals = []
for r in range(1, H):
    starts.append((r, -1))
    goals.append((r, W))

q = []
for r, c in starts:
    heappush(q, (0, r, c))

costs = defaultdict(lambda: 0)
for i in range(H):
    for j in range(W):
        c = A[i][j]
        costs[i, j] = c if c != -1 else INF

dists = defaultdict(lambda: INF)
while q:
    d, r, c = heappop(q)
    if dists[r, c] <= d: continue
    dists[r, c] = d
    if r < -1 or r > H: continue
    if c < -1 or c > W: continue

    for nr, nc in neighbors8(r, c):
        if nr in (0, H-1): continue
        if costs[nr, nc] == INF: continue

        nd = d + costs[nr, nc]
        if dists[nr, nc] <= nd: continue
        heappush(q, (nd, nr, nc))

ans = min(dists[r, c] for r, c in goals)
if ans == INF:
    print(-1)
else:
    print(ans)