package main
import (
"fmt"
"os"
"io/ioutil"
"strconv"
"math"
"github.com/skorobogatov/input"
)
var _ = ioutil.ReadFile;
var _ = strconv.ParseUint;
var _ = os.Args;
var _ = input.Scanf;
var _ = math.Sqrt;
var _ = fmt.Println;
const (
INF = 9999999;
)
type Vertex struct {
i int;
j int;
val int;
dist int;
index int;
}
type PriorityQueue struct {
heap []*Vertex;
cap int;
count int;
}
func (queue *PriorityQueue) empty() bool {
return queue.count == 0;
}
func (queue *PriorityQueue) insert(value *Vertex) {
i := queue.count;
if (i == queue.cap) {
if (queue.cap == 0) {
queue.cap = 1;
}
array := make([]*Vertex, queue.cap * 2);
copy(array, queue.heap);
queue.cap *= 2;
queue.heap = array;
}
queue.heap[i] = value;
queue.count++;
for (i > 0 && queue.heap[(i - 1)/2].dist > queue.heap[i].dist) {
queue.heap[(i-1)/2], queue.heap[i] = queue.heap[i], queue.heap[(i-1)/2];
queue.heap[i].index = i;
i = (i - 1)/2;
}
queue.heap[i].index = i;
}
func (queue *PriorityQueue) __heapify() {
var root int = 0;
for(true) {
var left int = 2 * root + 1;
var right int = left + 1;
var j int = root;
if (left < queue.count && queue.heap[root].dist > queue.heap[left].dist) {
root = left;
}
if (right < queue.count && queue.heap[root].dist > queue.heap[right].dist) {
root = right;
}
if (root == j) {
break;
}
queue.heap[j], queue.heap[root] = queue.heap[root], queue.heap[j];
queue.heap[j].index = j;
queue.heap[root].index = root;
}
}
func (queue *PriorityQueue) extractMin() *Vertex {
var tmp *Vertex = queue.heap[0];
queue.count--;
if (queue.count > 0) {
queue.heap[0] = queue.heap[queue.count];
queue.heap[0].index = 0;
queue.__heapify();
}
return tmp;
}
func (queue *PriorityQueue) decreaseKey(v *Vertex) {
i := v.index;
dist := v.dist;
for (i>0) && queue.heap[(i-1)/2].dist > dist {
queue.heap[i], queue.heap[(i-1)/2] = queue.heap[(i-1)/2], queue.heap[i];
queue.heap[i].index = int(i);
i = (i-1)/2;
}
queue.heap[i].index = int(i);
}
func main() {
var n int;
input.Scanf("%d", &n)
var matrix = make([][]Vertex, n)
for i := range matrix {
matrix[i] = make([]Vertex, n);
}
var q PriorityQueue;
var tmp int;
for i := range matrix {
for j:= range matrix {
input.Scanf("%d",&tmp);
u := &matrix[i][j];
u.dist = INF;
u.val = tmp;
u.i = i;
u.j = j;
q.insert(u);
}
}
matrix[0][0].dist = matrix[0][0].val;
next := func (v *Vertex, i, j int) {
if (i >= n || i < 0 || j >= n || j < 0) {
return;
}
u := &matrix[i][j];
if (u.index != -1 && v.dist + u.val < u.dist) {
u.dist = v.dist + u.val;
q.decreaseKey(u);
}
}
for !q.empty() {
v := q.extractMin();
v.index = -1;
next(v, v.i + 1, v.j);
next(v, v.i - 1, v.j);
next(v, v.i, v.j + 1);
next(v, v.i, v.j - 1);
}
fmt.Println(matrix[n-1][n-1].dist);
}