from sys import setrecursionlimit, stdin from collections import defaultdict, deque, Counter from itertools import permutations, combinations, product from functools import lru_cache from bisect import bisect_left, bisect_right from heapq import heappush, heappop from copy import copy, deepcopy from decimal import Decimal from random import random, randrange # from pypyjit import set_param # set_param('max_unroll_recursion=-1') setrecursionlimit(1 << 20) readline = stdin.readline INF = 10 ** 18 MOD = 998244353 # MOD = 1000000007 ALP = 26 ''' Input ''' def I(): return int(readline()) def ST(): return readline()[:-1] def LI(): return list(map(int, readline().split())) def LII(): return list(map(lambda x: int(x) - 1, readline().split())) def LF(x, func): return [func() for _ in [0] * x] def SPI(): return map(int, readline().split()) def SPII(): return map(lambda x: int(x) - 1, readline().split()) def FIE(x): return [readline()[:-1] for _ in [0] * x] ''' Array ''' def cmin(dp, i, x): if x < dp[i]: dp[i] = x def cmax(dp, i, x): if x > dp[i]: dp[i] = x ''' Alphabet ''' def alp_a_to_i(s): return ord(s) - ord('a') def alp_A_to_i(s): return ord(s) - ord('A') def alp_i_to_a(i): return chr(ord('a') + i) def alp_i_to_A(i): return chr(ord('A') + i) ''' Other''' def nynx(y, x, H, W): return [(y + dy, x + dx) for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)] if 0 <= y + dy < H and 0 <= x + dx < W] def gen(x, *args): if len(args) == 1: return [x] * args[0] if len(args) == 2: return [[x] * args[1] for _ in [0] * args[0]] if len(args) == 3: return [[[x] * args[2] for _ in [0] * args[1]] for _ in [0] * args[0]] if len(args) == 4: return [[[[x] * args[3] for _ in [0] * args[2]] for _ in [0] * args[1]] for _ in [0] * args[0]] ''' Output ''' def pprint(E): print() for e in E: print(e) def Yes(): print("Yes") def No(): print("No") def YES(): print("YES") def NO(): print("NO") def yn(x): print("Yes" if x else "No") def YN(x): print("YES" if x else "NO") ############################################################################################### class Dikstra: def __init__(self, N, node): self.node = node self.N = N def get(self, start): self.start_node = start dist, done = [10 ** 18] * self.N, [0] * self.N hq = [(0, start)] # (cost, node) dist[start] = 0 while hq: c, v = heappop(hq) if done[v]: continue done[v] = 1 for to, cost in self.node[v]: new_cost = dist[v] + cost if not done[to] and new_cost < dist[to]: dist[to] = new_cost heappush(hq, (dist[to], to)) return dist H, W = SPI() A = LF(H - 2, LI) A = [[-1] * W] + A + [[-1] * W] def f(i, j): return i * W + j def inside(y, x): return 0 <= y < H and 0 <= x < W node = [[] for _ in range(H * W)] for i in range(1, H - 1): for j in range(W): if A[i][j] == -1: continue if inside(i + 1, j) and A[i + 1][j] != -1: node[f(i, j)].append((f(i + 1, j), A[i + 1][j])) if inside(i - 1, j) and A[i - 1][j] != -1: node[f(i, j)].append((f(i - 1, j), A[i - 1][j])) if inside(i, j + 1) and A[i][j + 1] != -1: node[f(i, j)].append((f(i, j + 1), A[i][j + 1])) if inside(i + 1, j + 1) and A[i + 1][j + 1] != -1: node[f(i, j)].append((f(i + 1, j + 1), A[i + 1][j + 1])) if inside(i - 1, j + 1) and A[i - 1][j + 1] != -1: node[f(i, j)].append((f(i - 1, j + 1), A[i - 1][j + 1])) dist = [INF] * (H * W) done = [0] * (H * W) hq = [] for i in range(1, H - 1): if A[i][0] != -1: heappush(hq, (A[i][0], f(i, 0))) dist[f(i, 0)] = A[i][0] while hq: c, v = heappop(hq) if done[v]: continue done[v] = 1 for to, cost in node[v]: new_cost = dist[v] + cost if not done[to] and new_cost < dist[to]: dist[to] = new_cost heappush(hq, (dist[to], to)) ans = INF for i in range(1, H - 1): ans = min(ans, dist[f(i, W - 1)]) if ans == INF: ans = -1 print(ans)