package main import fmt os io ioutil strconv math github com skoroboga

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);
}