[백준 4485] 녹색 옷 입은 애가 젤다지?

from queue import PriorityQueue
import sys

def Dijkstra(G,sp):
    
    INF=float("inf")
    dist=[INF]
    prev=[0]
    Q=set()
    que=PriorityQueue()

    for i in range(1,len(G)):
        if i==sp:
            dist.append(0)
        else:
            dist.append(INF)
        prev.append(0)
        Q.add(i)
        que.put((dist[i],i))

    while Q!=set():
        while True:
            temp_u=que.get()[1]
            if temp_u in Q:
                u=temp_u
                break
        Q.remove(u)
        for i in range(1,len(G[u])+1):
            alt=dist[u]+G[u][i-1][1]
            if alt<dist[G[u][i-1][0]]:
                dist[G[u][i-1][0]]=alt
                prev[G[u][i-1][0]]=u
                que.put((alt,G[u][i-1][0]))
    
    return dist,prev

m=int(sys.stdin.readline())
ans=[]

while m:
    v=m*m
    n=m
    G=[[] for _ in range(v+1)]
    M=[sys.stdin.readline().strip().replace(" ","") for _ in range(m)]

    for i in range(n-1):
        for j in range(m):
            G[i+j*n+1].append((i+j*n+2,int(M[j][i+1])))

    for i in range(n):
        for j in range(m-1):
            G[i+j*n+1].append((i+j*n+1+n,int(M[j+1][i])))

    for i in range(1,n):
        for j in range(m):
            G[i+j*n+1].append((i+j*n,int(M[j][i-1])))

    for i in range(n):
        for j in range(1,m):
            G[i+j*n+1].append((i+j*n+1-n,int(M[j-1][i])))
    ans.append(Dijkstra(G,1)[0][n*m]+int(M[0][0]))
    m=int(sys.stdin.readline())
    

for i in range(len(ans)):
    print("Problem %d: %d" % (i+1,ans[i]))