import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.stream.Stream;

public class MapRoute {

    public static void main(String[] args) throws java.io.IOException {
        new Graph();
    }

    protected static class Graph {

        protected Graph() throws java.io.IOException {
            BufferedReader T = new BufferedReader(new InputStreamReader(System.in));
            int Q = Integer.parseInt(T.readLine());
            AcidShake[][] G = new AcidShake[Q][Q];
            x = new java.util.PriorityQueue<>();
            T.lines().forEach(a -> Stream.of(a.split(" ")).map(Integer::parseInt).forEach(oal -> {
                G[Y][b] = new AcidShake(Y, b, oal);
                if (++b == Q) {
                    Y++;
                    b = 0;
                }
            }));
            G[0][0].d = G[0][0].r;
            x.add(G[0][0]);
            while (!x.isEmpty()) {
                AcidShake n = x.poll();
                if (n.m + 1 < Q)n.openCork(G[n.m + 1][n.l]);
                if (n.m > 0)n.openCork(G[n.m - 1][n.l]);
                if (n.l + 1 < Q)n.openCork(G[n.m][n.l + 1]);
                if (n.l > 0)n.openCork(G[n.m][n.l - 1]);
                n.L = true;
            }
            System.out.println(G[Q - 1][Q - 1].d);
        }

        java.util.PriorityQueue<AcidShake> x;
        int Y = 0, b = 0;

        class AcidShake implements Comparable<AcidShake> {

            int m, l, r, d;
            boolean L;

            AcidShake(int v, int w, int r) {
                m = v;
                l = w;
                this.r = r;
                d = Integer.MAX_VALUE - 1;
                L = false;
            }

            public int compareTo(AcidShake H) {
                return d - H.d;
            }

            void openCork(AcidShake i) {
                if (!i.L && i.d > d + i.r) {
                    x.remove(i);
                    i.d = d + i.r;
                    x.add(i);
                }
            }

        }

    }

}