import heapq
        
N = int(input())
weight = []
for _ in range(N):
    weight.append([int(d) for d in input().split(" ")])
dist = [[float('inf') for _ in range(N)] for _ in range(N)]

dist[0][0] = weight[0][0]

q = [(dist[0][0], (0, 0))]
heapq.heapify(q)

while q:
    d, v = heapq.heappop(q)
    
    if d > dist[v[1]][v[0]]:
        continue
    
    if v[0] > 0: #left
        new_d = d + weight[v[1]][v[0]-1]
        if new_d < dist[v[1]][v[0]-1]:
            dist[v[1]][v[0]-1] = new_d
            heapq.heappush(q, (new_d, (v[0]-1,v[1])))
    if v[0] < N - 1: #right
        new_d = d + weight[v[1]][v[0]+1]
        if new_d < dist[v[1]][v[0]+1]:
            dist[v[1]][v[0]+1] = new_d
            heapq.heappush(q, (new_d, (v[0]+1,v[1])))
    if v[1] > 0: #up
        new_d = d + weight[v[1]-1][v[0]]
        if new_d < dist[v[1]-1][v[0]]:
            dist[v[1]-1][v[0]] = new_d
            heapq.heappush(q, (new_d, (v[0],v[1]-1)))
    if v[1] < N - 1: #down
        new_d = d + weight[v[1]+1][v[0]]
        if new_d < dist[v[1]+1][v[0]]:
            dist[v[1]+1][v[0]] = new_d
            heapq.heappush(q, (new_d, (v[0],v[1]+1)))
            
print(dist[-1][-1])

import heapq

def matrix_to_weighted_graph(matrix):
    rows, cols = len(matrix), len(matrix[0])
    graph = {}
    
    for i in range(rows):
        for j in range(cols):
            node = (i, j)  # Each element is a node
            neighbors = {}
            
            # Check and add valid neighbors with weights (value of neighboring element)
            if i > 0:  # Up
                neighbors[(i-1, j)] = matrix[i-1][j]
            if i < rows - 1:  # Down
                neighbors[(i+1, j)] = matrix[i+1][j]
            if j > 0:  # Left
                neighbors[(i, j-1)] = matrix[i][j-1]
            if j < cols - 1:  # Right
                neighbors[(i, j+1)] = matrix[i][j+1]
            
            graph[node] = neighbors
    graph[(cols-1, rows-1)] = {}
    return graph
    

def dijkstra(graph, source, target):
    # Initialize distances and priority queue
    distances = {vertex: float('infinity') for vertex in graph}
    distances[source] = 0
    priority_queue = [(0, source)]  # (distance, vertex)
    
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        # Skip if the distance is outdated
        if current_distance > distances[current_vertex]:
            continue
        
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            # If a shorter path is found
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances[target]
    
T = int(input())
matrix = []
for i in range(T):
    line = list(map(int, input().split()))
    matrix.append(line)
    
rows, cols = len(matrix), len(matrix[0])

graph = matrix_to_weighted_graph(matrix)
length = matrix[0][0] + dijkstra(graph, (0,0), (rows - 1, cols - 1))
print(length)

#include <bits/stdc++.h>
using namespace std;

typedef pair<long long, long long> Cell;

int N;

pair<int, int> dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<long long>> grid;


long long Dijkstra()
{
    priority_queue<Cell, vector<Cell>, greater<Cell>> Q;                    
    
    vector<long long> cost((N * N) + 1, 1e15);
    vector<pair<int, int>> M(N * N + 1);
    
    cost[0] = 0;
    
    long long index = 0;
    
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {            
            M[index] = {i, j};
            index++;                        
        }
    }    
    Q.push({grid[0][0], 0});
    
    while(!Q.empty())
    {
        long long cell = Q.top().second;
        long long currCost = Q.top().first;         
     
        if(cell == N * N - 1) return currCost;
        
        Q.pop();
        
        int y = M[cell].first;
        int x = M[cell].second;

        for(auto d : dir)
        {
            int next_y = y + d.first;
            int next_x = x + d.second;
            
            if(next_y < 0 || next_x < 0 || next_y >= N || next_x >= N) continue;
            
            long long nextCost = currCost + grid[next_y][next_x];
            long long next_index = (next_y * N) + next_x;
            
            if(nextCost < cost[next_index])
            {
                cost[next_index] = nextCost;
                Q.push({nextCost, next_index});
            }
        }
    }
    return cost[N * N - 1];
}

int main() 
{
    cin >> N;
    grid.resize(N, vector<long long>(N));    
    
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin >> grid[i][j];
        }
    }
    long long ans = Dijkstra();

    cout << ans;
    return 0;
}

long long dist[701][701];
list<pair<pair<int,int>,int>> graph[701][701];