<?php

function euler082($matrix, $n): int
{
    $graph = graph($matrix, $n);

    $length = count($graph);
    $distances = array_fill(0, $length, null);
    
    $target = $length - 1;
    $start = $target - 1;
    $pq = new MinPq();
    
    $distances[$start] = 0;
    $pq->insert($start, $distances[$start]);
    
    while (!$pq->isEmpty()) {
        list($curr, $dist) = $pq->extract();
        
        foreach ($graph[$curr] as $next => $next_dist) {
            $sum = $dist + $next_dist;
            if (is_null($distances[$next]) || $distances[$next] > $sum) {
                $distances[$next] = $sum;
                $pq->insert($next, $distances[$next]);
            }
        }
    }
    
    return $distances[$target];
}

function graph($matrix, $n) {
    $length = $n ** 2;
    $graph = [];
    
    $transforms = [
        # row, col, index
        [-1, 0, -$n],
        [0, -1, -1],
        [1, 0, $n],
        [0, 1, 1],
    ];
    
    // Connecting graph vertexes
    for ($index = 0; $index < $length; $index++) {
        list($row, $col) = ydiv($index, $n);
        foreach ($transforms as list($trow, $tcol, $tidx)) {
            $trow += $row;
            $tcol += $col;
            $tidx += $index;
            
            if (isset($matrix[$trow][$tcol])) {
                $dist = $matrix[$trow][$tcol];
                $graph[$index][$tidx] = $dist;
            }
        }
    }

    // Connecting start and target vertexes to first and last columns
    $start_index = $length;
    $target_index = $start_index + 1;
    for ($row = 0; $row < $n; $row++) {
        $first_col_idx = $row * $n;
        $last_col_idx = ($row + 1) * $n - 1;
        
        $graph[$start_index][$first_col_idx] = $matrix[$row][0];
        $graph[$first_col_idx][$start_index] = 0;
        
        $graph[$target_index][$last_col_idx] = $matrix[$row][$n - 1];
        $graph[$last_col_idx][$target_index] = 0;
    }

    return $graph;
}

class MinPq extends SplPriorityQueue
{
    public function __construct()
    {
        $this->setExtractFlags(self::EXTR_BOTH);
    }

    public function extract()
    {
        return array_values(parent::extract());
    }

    public function compare($a, $b)
    {
        return -($a <=> $b);
    }
}

function ydiv(int $a, int $b): array
{
    return [
        intval($a / $b),
        $a % $b,
    ];
}

function gets(): string
{
    return trim(fgets(STDIN));
}

function puts(string $str): void
{
    echo $str, PHP_EOL;
}

function logs($var): void
{
    ob_start();
    if (is_scalar($var)) {
        puts($var);
    } else {
        var_dump($var);
    }
    error_log(trim(ob_get_clean()));
}

$n = intval(gets());

for ($i = 0; $i < $n; $i++) {
    $matrix[$i] = array_map('intval', explode(' ', gets()));
}

puts(euler082($matrix, $n));