import std;

void main () {
    int H, W;
    readln.read(H, W);
    H -= 2;
    auto A = new int[][](H);
    foreach (i; 0 .. H) {
        A[i] = readln.split.to!(int[]);
    }

    // 1行目からH行目が非連結になるように壁を置く。
    // 壁はすごく迂回したりするかもしれないが、壁が輪のような形状を取ることはない。
    // すなわち、理想の壁において、始点からある壁にたどり着くpathは常に1通りになる。（2通り以上になるとき、自明にコストを削れる。）
    // 以上より、左側から右側への最短経路が解になる。

    auto cost = new long[][](H, W);
    foreach (i; 0 .. H) {
        cost[i][] = long.max;
    }
    auto pq = BinaryHeap!(Tuple!(int, int, long)[], "b[2] < a[2]")([]);
    foreach (i; 0 .. H) {
        if (A[i][0] != -1) {
            cost[i][0] = A[i][0];
            pq.insert(tuple(i, 0, 1L * A[i][0]));
        }
    }

    const dxy = [
        [0, 1],
        [0, -1],
        [1, 0],
        [-1, 0],
        [1, 1],
        [1, -1],
        [-1, 1],
        [-1, -1]
    ];
    bool isIn (int y, int x) {
        return 0 <= y && y < H && 0 <= x && x < W;
    }

    while (!pq.empty()) {
        auto top = pq.front();
        pq.removeFront();
        int y = top[0];
        int x = top[1];
        long c = top[2];
        if (cost[y][x] < c) {
            continue;
        }

        foreach (d; dxy) {
            int ny = y + d[0];
            int nx = x + d[1];
            if (!isIn(ny, nx) || A[ny][nx] == -1) {
                continue;
            }
            long nc = c + A[ny][nx];

            if (nc < cost[ny][nx]) {
                cost[ny][nx] = nc;
                pq.insert(tuple(ny, nx, nc));
            }
        }
    }

    long ans = long.max;
    foreach (i; 0 .. H) {
        ans = min(ans, cost[i][W - 1]);
    }

    writeln(ans == long.max ? -1 : ans);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}