import java.nio.file.*;
import java.util.*;

public class Euler83 {
    public static void main(String[] args) throws Exception {
        List<String> lines = Files.readAllLines(Path.of("resources/documents/0083_matrix.txt"));
        int n = lines.size();
        int[][] m = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] p = lines.get(i).trim().split(",");
            for (int j = 0; j < n; j++)
                m[i][j] = Integer.parseInt(p[j]);
        }
        int[][] dist = new int[n][n];
        for (int[] r : dist)
            Arrays.fill(r, Integer.MAX_VALUE);
        dist[0][0] = m[0][0];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[] { m[0][0], 0, 0 });
        int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
        while (!pq.isEmpty()) {
            int[] c = pq.poll();
            int d = c[0], i = c[1], j = c[2];
            if (d > dist[i][j])
                continue;
            for (int[] dir : dirs) {
                int ni = i + dir[0], nj = j + dir[1];
                if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                    int nd = d + m[ni][nj];
                    if (nd < dist[ni][nj]) {
                        dist[ni][nj] = nd;
                        pq.add(new int[] { nd, ni, nj });
                    }
                }
            }
        }
        System.out.println(dist[n - 1][n - 1]);
    }
}