[4485] 녹색 옷 입은

import java.io.*;
import java.util.*;

public class Main {
	static int N, INF, arr[][], dp[][];
	static int[] idx = { 0, 0, -1, 1 };
	static int[] idy = { 1, -1, 0, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int TC = 1;
		while (true) {
			N = Integer.parseInt(br.readLine());
			if (N == 0)
				break;

			arr = new int[N][N];
			dp = new int[N][N];
			INF = 125 * 10;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
					dp[i][j] = INF;
				}
			}

			sb.append("Problem ").append(TC++).append(": ").append(fn()).append("\n");

		}

		System.out.println(sb);

	}

	public static int fn() {
		PriorityQueue<Position> pq = new PriorityQueue<>();
		boolean[][] visit = new boolean[N][N];
		pq.add(new Position(0, 0, arr[0][0]));
		dp[0][0] = arr[0][0];

		while (!pq.isEmpty()) {
			Position p = pq.poll();

			if(p.x==N-1 && p.y==N-1) return dp[p.x][p.y];
			
			if (visit[p.x][p.y])
				continue;
			visit[p.x][p.y] = true;
			for (int i = 0; i < 4; i++) {
				int sx = idx[i] + p.x;
				int sy = idy[i] + p.y;

				if (sx >= 0 && sx < N && sy >= 0 && sy < N) {
					if (dp[sx][sy] > dp[p.x][p.y] + arr[sx][sy]) {
						dp[sx][sy] = dp[p.x][p.y] + arr[sx][sy];
						pq.add(new Position(sx, sy, dp[sx][sy]));
					}
				}
			}
		}

		return dp[N - 1][N - 1];

	}

	public static class Position implements Comparable<Position> {
		int x;
		int y;
		int cost;

		public Position(int x, int y, int cost) {
			super();
			this.x = x;
			this.y = y;
			this.cost = cost;
		}

		@Override
		public int compareTo(Position o) {
			// TODO Auto-generated method stub
			return cost - o.cost;
		}

	}

}