#グラフの最短パス.Dijkstra

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
5
0 2 2 5 9
2 0 3 4 8
2 3 0 7 6
5 4 7 0 5
9 8 6 5 0

output==> 8
*/

public class 다익스트라 {
	
	static int N, INF = Integer.MAX_VALUE;
	static int[] dis;
	static int[][] matrix;
	static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		matrix = new int[N][N];
		dis = new int[N];
		visited = new boolean[N];
		Arrays.fill(dis, INF);
		
		StringTokenizer st = null;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dis[0] = 0;
		int min = 0;
		int current = 0;
		while(true) {
			min = INF;
			// 1단계. 방문하지 않은 정점들 중 출발지에서 자신까지 오는 비용이 최단인 정점을 선택
			for(int i=0; i<N; i++) {
				if(visited[i]) continue;
				if(min > dis[i]) {
					// 최소인 정점 정보를 저장
					min = dis[i];
					current = i;
				}
			}
			
			visited[current] = true;
			if(current == N-1) break;
			
			//2단계. 선택된 정점을 경유지로 하는 거리 정보 업데이트
			for(int i=0; i<N; i++) {
				if(visited[i] || matrix[current][i] == 0) continue;
				// min => dis[current]
				dis[i] = Math.min(dis[i], matrix[current][i] + min);
			}
		}
		
		System.out.println(dis[N-1]);
	
	}

}

public class 다익스트라 {
	
	static int N, INF = Integer.MAX_VALUE;
	static int[] dis;
	static int[][] matrix;
	static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		matrix = new int[N][N];
		dis = new int[N];
		visited = new boolean[N];
		Arrays.fill(dis, INF);
		
		StringTokenizer st = null;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// index, weight
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[1], o2[1]);
			}
		});
		
		pq.add(new int[] {0,0});
		while(true) {
			// 1단계. 방문하지 않은 정점들 중 출발지에서 자신까지 오는 비용이 최단인 정점을 선택
			int[] cur = pq.poll();
			int curidx = cur[0];
			int minWeight = cur[1];
			if(visited[curidx]) continue; 	//이미 최소값으로 처리된 정점 
			
			dis[curidx] = minWeight;
			visited[curidx] = true;
			if(curidx == N-1) break;
			
			//2단계. 선택된 정점을 경유지로 하는 거리 정보 업데이트
			for(int i=0; i<N; i++) {
				if(visited[i] || matrix[curidx][i] == 0) continue;
				// min => dis[current]
				dis[i] = Math.min(dis[i], matrix[curidx][i] + minWeight);
				pq.add(new int[] {i,dis[i]});
			}
		}
		
		System.out.println(dis[N-1]);
	
	}

}