dijkstra

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

class Dijkstra {
    ArrayList<Vertex> vertices;
    int first;

    Dijkstra(int[][] map, int n) {
        first = map[0][0];

        this.vertices = new ArrayList<>();

        for (int i = 0; i < n * n; i++)
            vertices.add(new Vertex());

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j < n - 1) {
                    vertices.get(i + i * (n - 1) + j).to.add(vertices.get(i + i * (n - 1) + j + 1));
                    vertices.get(i + i * (n - 1) + j).weights.add(map[i][j + 1]);
                }
                if (i < n - 1) {
                    vertices.get(i + i * (n - 1) + j).to.add(vertices.get(i + i * (n - 1) + j + n));
                    vertices.get(i + i * (n - 1) + j).weights.add(map[i + 1][j]);
                }
                if (j > 0 && i > 0 && i < n - 1) {
                    vertices.get(i + i * (n - 1) + j).to.add(vertices.get(i + i * (n - 1) + j - 1));
                    vertices.get(i + i * (n - 1) + j).weights.add(map[i][j - 1]);
                }
                if (i > 0 && j > 0 && j < n - 1) {
                    vertices.get(i + i * (n - 1) + j).to.add(vertices.get(i + i * (n - 1) + j - n));
                    vertices.get(i + i * (n - 1) + j).weights.add(map[i - 1][j]);
                }
            }
        }
    }

    private boolean relax(Vertex u, Vertex v, int w) {
        boolean changed = (u.dist + w) < v.dist;

        if (changed) {
            v.dist = u.dist + w;
            v.parent = u;
        }

        return changed;
    }

    void useAlgorithm() {
        PriorityQueue<Vertex> q = new PriorityQueue<>((o1, o2) -> (int) (o1.dist - o2.dist));

        Vertex s = this.vertices.get(0);
        s.dist = 0;
        q.add(vertices.get(0));

        while(!q.isEmpty()) {
            Vertex v = q.poll();

            for (int i = 0; i < v.to.size(); i++){
                Vertex u = v.to.get(i);
                if (relax(v, u, v.weights.get(i))) {
                    q.remove(u);
                    q.add(u);
                }
            }
        }
    }
}

class Vertex {
    Vertex parent;
    double dist;
    ArrayList<Vertex> to;
    ArrayList<Integer> weights;

    Vertex() {
        this.parent = null;
        this.dist = Double.POSITIVE_INFINITY;
        this.to = new ArrayList<>();
        this.weights = new ArrayList<>();
    }
}

public class MapRoute {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                map[i][j] = in.nextInt();

        double start = System.currentTimeMillis();

        Dijkstra dijkstra = new Dijkstra(map, n);

        dijkstra.useAlgorithm();

        System.out.println((int) dijkstra.vertices.get(n * n - 1).dist + dijkstra.first);

        double end = System.currentTimeMillis();

        System.out.println((end - start)/1000);
    }
}