Problem:
 Score : 400 points    Problem Statement Joisino the magical girl has decided to turn every single digit that exists on this world into 1 .  Rewriting a digit i with j  (0≤i,j≤9) costs c_{i,j} MP (Magic Points).  She is now standing before a wall. The wall is divided into HW squares in H rows and W columns, and at least one square contains a digit between 0 and 9 (inclusive).  You are given A_{i,j} that describes the square at the i -th row from the top and j -th column from the left, as follows:   If A_{i,j}≠-1 , the square contains a digit A_{i,j} .  If A_{i,j}=-1 , the square does not contain a digit.   Find the minimum total amount of MP required to turn every digit on this wall into 1 in the end.      Constraints  1≤H,W≤200  1≤c_{i,j}≤10^3  (i≠j)  c_{i,j}=0  (i=j)  -1≤A_{i,j}≤9  All input values are integers.  There is at least one digit on the wall.         Input Input is given from Standard Input in the following format:  H  W  c_{0,0}  ...  c_{0,9}  :  c_{9,0}  ...  c_{9,9}  A_{1,1}  ...  A_{1,W}  :  A_{H,1}  ...  A_{H,W}       Output Print the minimum total amount of MP required to turn every digit on the wall into 1 in the end.        Sample Input 1 2 4
0 9 9 9 9 9 9 9 9 9
9 0 9 9 9 9 9 9 9 9
9 9 0 9 9 9 9 9 9 9
9 9 9 0 9 9 9 9 9 9
9 9 9 9 0 9 9 9 9 2
9 9 9 9 9 0 9 9 9 9
9 9 9 9 9 9 0 9 9 9
9 9 9 9 9 9 9 0 9 9
9 9 9 9 2 9 9 9 0 9
9 2 9 9 9 9 9 9 9 0
-1 -1 -1 -1
8 1 1 8      Sample Output 1 12  To turn a single 8 into 1 , it is optimal to first turn 8 into 4 , then turn 4 into 9 , and finally turn 9 into 1 , costing 6 MP.  The wall contains two 8 s, so the minimum total MP required is 6×2=12 .       Sample Input 2 5 5
0 999 999 999 999 999 999 999 999 999
999 0 999 999 999 999 999 999 999 999
999 999 0 999 999 999 999 999 999 999
999 999 999 0 999 999 999 999 999 999
999 999 999 999 0 999 999 999 999 999
999 999 999 999 999 0 999 999 999 999
999 999 999 999 999 999 0 999 999 999
999 999 999 999 999 999 999 0 999 999
999 999 999 999 999 999 999 999 0 999
999 999 999 999 999 999 999 999 999 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1      Sample Output 2 0  Note that she may not need to change any digit.       Sample Input 3 3 5
0 4 3 6 2 7 2 5 3 3
4 0 5 3 7 5 3 7 2 7
5 7 0 7 2 9 3 2 9 1
3 6 2 0 2 4 6 4 2 3
3 5 7 4 0 6 9 7 6 7
9 8 5 2 2 0 4 7 6 5
5 4 6 3 2 3 0 5 4 3
3 6 2 3 4 2 4 0 8 9
4 6 5 4 3 5 3 2 0 8
2 1 3 4 5 7 8 6 4 0
3 5 2 6 1
2 5 3 2 1
6 9 2 5 6      Sample Output 3 47

Solution (Python):
import heapq


class PriorityQueue:
    def __init__(self):
        self.__heap = []
        self.__count = 0

    def empty(self) -> bool:
        return self.__count == 0

    def dequeue(self):
        if self.empty():
            raise Exception('empty')
        self.__count -= 1
        return heapq.heappop(self.__heap)

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__heap, v)

    def __len__(self):
        return self.__count


def dijkstra(s: int, t: int, V: int, edges: list) -> int:
    '''dijkstra method
    :param s: start
    :param t: finish
    :param V: number of vertexes
    :param edges: collection of edges
    :return: minimum distance from u to v
    '''
    d = [float('inf')] * V
    d[s] = 0

    q = PriorityQueue()
    q.enqueue((d[s], s))

    while not q.empty():
        _, u = q.dequeue()
        for v, cost in edges[u]:
            alt = d[u] + cost

            if alt < d[v]:
                d[v] = alt
                q.enqueue((d[v], v))

    return d[t]


def wall(H: int, W: int, C: list, A: list) -> int:
    
    edges = [[(v, C[u][v]) for v in range(10)] for u in range(10)]
    min_dist = [dijkstra(i, 1, 10, edges) for i in range(10)]

    return sum(
        min_dist[a]
        for row in A
        for a in row if a >= 0)


if __name__ == "__main__":
    H = 0
    H, W = map(int, input().split())
    C = [[int(s) for s in input().split()] for _ in range(10)]
    A = [[int(s) for s in input().split()] for _ in range(H)]
    ans = wall(H, W, C, A)
    print(ans)

Solution (Python):
import sys

def warshall_floyd(d):
    n = len(d)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])
    return d


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = [[int(c) for c in input().split()] for _ in range(10)]
    A = [list(map(int, input().split())) for _ in range(H)]

    d = warshall_floyd(C)

    ans = 0
    for a in A:
        for i in a:
            if i == -1:
                continue
            ans += d[i][1]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = [[int(c) for c in input().split()] for _ in range(10)]
    A = [list(map(int, input().split())) for _ in range(H)]

    dp = [[10**4] * 10 for _ in range(10)]
    for i in range(10):
        for j in range(10):
            for k in range(10):
                C[j][k] = min(C[j][k], C[j][i] + C[i][k])

    ans = 0
    for a in A:
        for i in a:
            if i == -1:
                continue
            ans += C[i][1]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys

def main():
	H, W = map(int, input().split(" "))
	MP = []
	for _ in range(10):
		tmp = input().split(" ")
		tmp = [int(s) for s in tmp]
		MP.append(tmp)
	
	MP = warshall_floyd(MP, 10)
	
	ans = 0
	for _ in range(H):
		tmp = input().split(" ")
		tmp = [int(s) for s in tmp]
		for i, val in enumerate(tmp):
			if val == -1:
				continue
			ans += MP[val][1]
		
	print(ans)
	
def warshall_floyd(d, n):
	
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j],d[i][k] + d[k][j])
	return d
	
if __name__ == "__main__":
	main()

Solution (Python):
from itertools import chain
from collections import Counter
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
A = Counter(list(chain.from_iterable([list(map(int, input().split())) for _ in range(H)])))
for _ in range(100):
    for i in range(10):
        for j in range(10):
            c = min([C[i][k] + C[k][j] for k in range(10)])
            C[i][j] = min(c, C[i][j])
num = 0
for i, n in A.items():
    if i == -1:
        continue
    num += C[i][1] * n
print(num)

Solution (Python):



def main():
    h, w = map(int, input().split())
    c = [list(map(int, input().split())) for _ in range(10)]
    a = [list(map(int, input().split())) for _ in range(h)]
    ans = 0

    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])

    for x in range(h):
        for y in range(w):
            pos = a[x][y]

            if pos >= 0:
                ans += c[pos][1]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import copy
H,W=map(int,input().split())
C=[list(map(int,input().split())) for _ in range(10)]
A=[list(map(int,input().split())) for _ in range(H)]
def DP(i,check,x):
    s=C[i][1]
    for c in range(10):
        if c!=i and check[c]!=1 and C[i][c]<C[i][1]:
            t=copy.deepcopy(check)
            t[c]=1
            s=min(s,C[i][c]+DP(c,t,x))
    return x+s
B=[0]*10
for i in range(10):
    if i!=1:
        B[i]=DP(i,[1 if t==1 or t==i else 0 for t in range(10)],0)
D=[0]*10
for h in range(H):
    for w in range(W):
        if A[h][w]!=-1:
            D[A[h][w]]+=1
print(sum([B[i]*D[i] for i in range(10)]))

Solution (Python):
def warshall_floyd(graph):
    dist = [[1e9 for i in range(10)] for k in range(10)]
    for i in range(10):
        dist[i][i] = 0
    for i in graph:
        for k in range(9):
            dist[i][graph[i][k][0]] = graph[i][k][1]
    for i in range(10):
        for k in range(10):
            for j in range(10):
                dist[k][j] = min(dist[k][j],dist[k][i] + dist[i][j])
    return dist


h,w = map(int,input().split())
graph = dict()
for i in range(10):
    graph[i] = []

for i in range(10):
    temp = list(map(int,input().split()))
    for k in range(10):
        if i != k:
            graph[i].append([k,temp[k]])
dist = warshall_floyd(graph)
a = []
ans = 0
for i in range(h):
    temp = list(map(int,input().split()))
    for k in range(w):
        if temp[k] > 1 or temp[k] == 0:
            ans += dist[temp[k]][1]
print(ans)

Solution (Python):
def wf(d):
    n = 10
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j] , d[i][k] + d[k][j])

    return(d)

H,W = map(int,input().split())

c = []
for i in range(10):
    c.append(list(map(int,input().split())))

A = {}
for i in range(H):
    for j in list(map(int,input().split())):
        if j == -1:
            continue
        if j not in A.keys():
            A[j] = 0
        A[j] += 1


d = wf(c)
ans = 0
for key in A.keys():
    if key != 1:
        ans += A[key]*d[key][1]

print(ans)

Solution (Python):
def wf(c):
    d = {}
    for i in range(10):
        for j in range(10):
            d[(i,j)] = c[i][j]
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if d[(i,j)] > d[(i,k)] + d[(k,j)]:
                    d[(i,j)] = d[(i,k)] + d[(k,j)]
    e = {}
    for i in range(10):
        e[i] = d[(i,1)]
    return e


def solve(H, W, c, A):
    d = wf(c)
    mp = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                mp += d[A[i][j]]
    return mp


def main():
    H, W = list(map(int, input().split(' ')))
    c = []
    for i in range(10):
        c.append(list(map(int, input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, input().split(' '))))

    ans = solve(H, W, c, A)
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(10)]
wall = [list(map(int, input().split())) for _ in range(h)]

dis = [0] * 10
s = {1}
u = {0,2,3,4,5,6,7,8,9}
for i in range(10):
    dis[i] = cost[i][1]
for _ in range(10):
    if u == set():
        break
    mindis = 10**9
    for i in u:
        if dis[i] < mindis:
            a = i
            mindis = dis[i]
    u.remove(a)
    s.add(a)
    for i in u:
        dis[i] = min(dis[i], dis[a] + cost[i][a])
count = {}
for i in range(h):
    for j in range(w):
        if wall[i][j] >= 0:
            if wall[i][j] not in count:
                count[wall[i][j]] = 1
            else:
                count[wall[i][j]] += 1
ans = 0
for i, c in count.items():
    ans += dis[i] * c
print(ans)

Solution (Python):

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w=IL()
c=[IL() for i in range(10)]
a=[IL() for i in range(h)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
    
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1:
            continue
        ans+=c[a[i][j]][1]
print(ans)

Solution (Python):
h, w = map(int, input().split())

cmap = []
for _ in range(10):
  cmap.append(list(map(int, input().split())))

amap = []
for _ in range(h):
  amap.append(list(map(int, input().split())))

for k in range(10):
  for i in range(10):
    for j in range(10):
      if cmap[i][j] > cmap[i][k] + cmap[k][j]:
        cmap[i][j] = cmap[i][k] + cmap[k][j]

ans = 0
for alist in amap:
  for a in alist:
    if a != -1:
      ans += cmap[a][1]

print(ans)

Solution (Python):
def warshall_floyd(d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
  
h,w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
a = [list(map(int, input().split())) for i in range(h)]
ans = 0

cost = warshall_floyd(c)

for i in range(h):
  for j in range(w):
    if a[i][j] != -1:
      ans += cost[a[i][j]][1]

print(ans)

Solution (Python):
def warshall_floyd(graph):
    num_v = len(graph)
    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    return graph


H, W = map(int, input().split())
items = []
for i in range(10):
    items.append(list(map(int, input().split())))

a_list = []
for i in range(H):
    a_list.append(tuple(map(int, input().split())))
graph = warshall_floyd(items)

ans = 0
for a in a_list:
    for item in a:
        if item == -1:
            continue
        ans += graph[item][1]
print(ans)

Solution (Python):
def warshall_floyd(d, V): 
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
                
    return d
                
H, W = map(int, input().split())                
L = [list(map(int, input().split())) for _ in range(10)]
a = [list(map(int, input().split())) for _ in range(H)]

cost = warshall_floyd(L, 10)

res = 0
for i in range(H):
    for j in range(W):
        if a[i][j] != -1:
            res += cost[a[i][j]][1]
        
print(res)

Solution (Python):
import numpy as np
H, W = map(int, input().split())
mC = np.zeros((10, 10), dtype=int)
for i in range(10):
    mC[i] = list(map(int, input().split()))
A = []
for _ in range(H):
    A += list(map(int, input().split()))
from collections import Counter
cnt9 = Counter(A)
del cnt9[-1]

for i in range(10):
    mC = np.minimum(mC, mC[i: i + 1] + mC[:, i: i + 1])

ans = 0
for i, cnt in cnt9.items():
    ans += mC[i, 1] * cnt

print(ans)

Solution (Python):
import sys
import itertools
input = sys.stdin.readline
def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
n = 10
h,w = map(int,input().split())
d = [[] for i in range(10)] 

for i in range(10):
    d[i] = list(map(int,input().split()))

d = warshall_floyd(d)

res = 0
for i in range(h):
    p = tuple(map(int,input().split()))
    for e in p:
        if e == -1:
            continue
        res += d[e][1]
print(res)

Solution (Python):
import itertools
H,W = map(int,input().split())
C = [list(map(int,input().split())) for i in range(10)]
bit = [0]*10
for i in range(H):
    s = input().split()
    for j in range(W):
        if int(s[j]) == -1: continue
        bit[int(s[j])] += 1


def warshall_floyd(dist,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k]+dist[k][j]:
                    dist[i][j] = dist[i][k]+dist[k][j]

warshall_floyd(C,10)
ans = 0
for i in range(10):
    ans += C[i][1]*bit[i]
print(ans)

Solution (Python):
h,w = map(int,input().split())
ij = [list(map(int,input().split())) for x in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            ij[i][j] = min(ij[i][j],ij[i][k]+ij[k][j])
ans = 0
for i in range(h):
    for j in list(map(int,input().split())):
        if j == -1:continue
        ans += ij[j][1]
print(ans)

Solution (Python):
H,W = map(int, input().split())
c = [ [int(j) for j in input().split()] for _ in range(10)]


from collections import defaultdict
d = defaultdict(int)

dist = [ [float("inf")] * 10 for _ in range(10)]
for i in range(10):
    for j in range(10):
        dist[i][j] = c[i][j]
for k in range(10):
    for i in range(10):
        for j in range(10):
            dist[i][j] = min(dist[i][j], 
                    dist[i][k] + dist[k][j] )


A = [ [int(j) for j in input().split()] for _ in range(H)]
for ai in A:
    for aij in ai:
        d[aij] += 1
ans = 0
for i in range(0,10):
    if i == 1: continue
    ans += d[i]* dist[i][1]
print(ans)

Solution (Python):
H, W = map(int, input().split())
C = [[] for i in range(10)]
A = [[] for i in range(H)]
for i in range(10):
    c = list(map(int, input().split()))
    C[i] = c

for i in range(H):
    a = list(map(int, input().split()))
    A[i] = a

for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])

num = 0
for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            num += C[A[i][j]][1]

print(num)

Solution (Python):
N, M = map(int, input().split())
inf = float("inf")
dp = [[inf]*100 for _ in [0]*100]
for i in range(10):dp[i][i] = 0
d = [list(map(int, input().split())) for i in range(10)]
m = [list(map(int, input().split())) for i in range(N)]
ans = 0
 
for i in range(10):
    for j in range(10):
        dp[i][j] = d[i][j]
for k in range(10):
    for i in range(10):
        for j in range(10):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])
c=0
for i in range(N):
    for j in range(M):
        if m[i][j] != 1 :
            if m[i][j] != -1 :
                c+=dp[m[i][j]][1]
print(c)

Solution (Python):
H, W = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j], c[i][k] + c[k][j])
ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] != -1:
            ans += c[A[h][w]][1]
print(ans)

Solution (Python):
L = []
ans = 0
x,y = map(int,input().split())
for _ in range(10):
    l = list(map(int, input().split()))
    L.append(l)

def warshall_floyd(n,w,d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

d = [[float("inf") for i in range(10)] for i in range(10)] 
for i in range(10):
    for j in range(10): 
        d[i][j] = L[i][j]
for i in range(10):
    d[i][i] = 0 
w =  warshall_floyd(10,10,d)
for _ in range(x):
    s = list(map(int, filter(lambda x:x!="-1",input().split())))
    for x in s:
     
        ans += w[x][1]
print(ans)

Solution (Python):
h,w = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
a = [list(map(int,input().split())) for i in range(h)]
 
len_c = len(c)


for k in range(len_c):
  for i in range(len_c):
    for j in range(len_c):
      c[i][j] = min(c[i][j], c[i][k]+c[k][j])
 
ans =0
for i in range(h):
  for j in range(w):
    if a[i][j]==-1:
      ans += 0
    else:
      ans += c[a[i][j]][1]
      
print(ans)

Solution (Python):
h,w = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
a = [list(map(int,input().split())) for i in range(h)]




len_c = len(c)
cost = [[float('inf')]*len_c for i in range(len_c)]

for k in range(len_c):
  for i in range(len_c):
    for j in range(len_c):
      c[i][j] = min(c[i][j], c[i][k]+c[k][j])

ans =0
for i in range(h):
  for j in range(w):
    if a[i][j]==-1:
      ans += 0
    else:
      ans += c[a[i][j]][1]
      
print(ans)

Solution (Python):
H,W=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(10)]
A=[list(map(int,input().split())) for _ in range(H)]

from itertools import product

for k,i,j in product(range(10),repeat=3):
    if c[i][j] > c[i][k]+c[k][j]:
        c[i][j] = c[i][k]+c[k][j]
ans=0

for i,j in product(range(H),range(W)):
    if A[i][j]!=-1:
        ans+=c[A[i][j]][1]
print(ans)

Solution (Python):
H,W=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(10)]
A=[list(map(int,input().split())) for _ in range(H)]

mincost=[0 for i in range(10)]

for i in range(10):
    if i!=1:
        res = {i:0}
        path = [(j,c[i][j]) for j in range(10) if j not in res.keys()]
        while 1 not in res.keys():
            path.sort(key=lambda x:x[1])
            node,cost=path[0]
            res[node]=cost
            path = [p for p in path if p[0] not in res.keys()]
            path += [(j,cost+c[node][j]) for j in range(10) if j not in res.keys()]
        mincost[i]=res[1]

ans=0
from itertools import product
for i,j in product(range(H),range(W)):
    if A[i][j]!=-1:
        ans+=mincost[A[i][j]]
print(ans)

Solution (Python):
h,w=map(int,input().split())
c=[list(map(int,input().split())) for i in range(10)]
a=[list(map(int,input().split())) for i in range(h)]
 
for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])

ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1:
            ans+=c[a[i][j]][1]
print(ans)

Solution (Python):
H,W = list(map(int,input().split()))
c = [list(map(int,input().split())) for i in range(10)]
A = [list(map(int,input().split())) for i in range(H)]


for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j],c[i][k]+c[k][j])

ans = 0

for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            ans += c[A[i][j]][1]

print(ans)

Solution (Python):
class Graph(object):

    class Edge:
        def __init__(self, to: int, cost: int):
            self.to = to
            self.cost = cost

        def __str__(self):
            return "Edge: (to " + str(self.to) + ", cost " + str(self.cost) + ")"

        def __repr__(self):
            return self.__str__()

    INF = 10e10

    def __init__(self, node_n: int):
        self.node_n = node_n
        self.edges = [{} for _ in range(self.node_n)]
        self.dist = [self.INF for _ in range(self.node_n)]

    def set_edge(self, from_pos: int, to_pos: int, cost: int, reversible: bool) -> None:
        self.edges[from_pos][to_pos] = self.Edge(to_pos, cost)
        if reversible:
            self.edges[to_pos][from_pos] = self.Edge(from_pos, cost)

    def solve(self) -> list:
        raise NotImplementedError


class WarshallFloyd(Graph):
    def solve(self) -> None:
        for via_p in range(self.node_n):
            for from_p in range(self.node_n):
                for to_p in range(self.node_n):
                    if via_p in self.edges[from_p].keys() and to_p in self.edges[via_p].keys():
                        alt = self.edges[from_p][via_p].cost + self.edges[via_p][to_p].cost
                        if to_p not in self.edges[from_p]:
                            self.edges[from_p][to_p].cost = alt
                        else:
                            self.edges[from_p][to_p].cost = min(self.edges[from_p][to_p].cost, alt)


if __name__ == '__main__':
    H, W = map(int, input().split())
    graph = WarshallFloyd(10)

    for i in range(10):
        buff = [int(i) for i in input().split()]
        for j in range(10):
            graph.set_edge(i, j, buff[j], False)

    graph.solve()

    A = [[int(j) for j in input().split()] for _ in range(H)]
    ans = sum(map(lambda l:
                  sum(map(lambda e:
                          0 if e == -1 else graph.edges[e][1].cost
                          , l))
                  , A))
    print(ans)

Solution (Python):
h,w = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(10)]

for i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k] = min(c[j][k], c[j][i] + c[i][k])

ans = 0
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        if a[j] != -1:
            ans += c[a[j]][1]
print(ans)

Solution (Python):
h,w = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(10)]

for i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k] = min(c[j][k], c[j][i] + c[i][k])

ans = 0
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        if a[j] >= 0:
            ans += c[a[j]][1]
print(ans)

Solution (Python):
H, W = (list)(map(int, input().split()))
N = 10
mp = [[l for l in (list)(map(int, input().split()))] for _ in range(N)]

wall = [[l for l in (list)(map(int, input().split()))] for _ in range(H)]


def dijkstra(s, g):
    '''
        s:start node
        g:foal node
        return cost from s to g
    '''
    return 0


def war(mp):
    for i in range(N):
        for j in range(N):
            for k in range(N):
                mp[j][k] = min(mp[j][k], mp[j][i]+mp[i][k])
    return mp


mp = war(mp)
cost = 0
for l in wall:
    for i in l:
        if i == -1:
            continue
        else:
            cost += mp[i][1]
print(cost)

Solution (Python):
H, W = (list)(map(int, input().split()))
N = 10
mp = [[l for l in (list)(map(int, input().split()))] for _ in range(N)]

wall = [[l for l in (list)(map(int, input().split()))] for _ in range(H)]


def dijkstra(s, g):
    '''
        s:start node
        g:foal node
        return cost from s to g
    '''
    return 0


def war(mp):
    for i in range(N):
        for j in range(N):
            for k in range(N):
                mp[j][k] = min(mp[j][k], mp[j][i]+mp[i][k])
    return mp


mp = war(mp)
cost = 0
for l in wall:
    for i in l:
        if i == -1:
            continue
        else:
            cost += mp[i][1]
print(cost)

Solution (Python):
H, W = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            if c[i][j] > c[i][k]+c[k][j]:
                c[i][j] = c[i][k] + c[k][j]

ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            ans += c[A[i][j]][1]
print(ans)

Solution (Python):
def inpl(): return list(map(int, input().split()))


H, W = inpl()

cost = [inpl() for _ in range(10)]

in_set = {1}
to_cost = [10**3 for i in range(10)]
to_cost[1] = 0
for _ in range(1, 10):
    bridge = {}
    for i in in_set:
        tmp_cost = 10 ** 4
        for j in range(10):
            if j in in_set or i == j:
                continue
            if cost[j][i] < tmp_cost:
                tmp_cost = cost[j][i]
                tmp_comer = j
        bridge[(i, tmp_comer)] = to_cost[i] + tmp_cost
    tt = min(bridge, key=bridge.get)
    to_cost[tt[1]] = bridge[tt]
    
    in_set.add(tt[1])




ans = 0
for _ in range(H):
    ans += sum(to_cost[i] for i in inpl() if i != -1)
print(ans)

Solution (Python):
import heapq


class dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.visited = [-1 for i in range(len(adj))]
        self.heap = []

    def allSearch(self, _start):
        
        heapq.heappush(self.heap, [0, _start])
        
        while 1:
            if len(self.heap) == 0:
                break
            start = heapq.heappop(self.heap)
            
            if self.visited[start[1]] != -1:
                continue
            
            self.visited[start[1]] = start[0]
            for i in range(len(self.adj)):
                if self.visited[i] == -1 and self.adj[start[1]][i] != 0:
                    heapq.heappush(self.heap, [self.adj[start[1]][i] + self.visited[start[1]], i])
        
        return self.visited


def func(h, w, c, a):
    cost = [0 for _ in range(10)]
    for i in range(len(c)):
        dij = dijkstra(adj=c)
        cost[i] = dij.allSearch(i)[1]
    
    totalCost = 0
    for i in range(len(a)):
        for j in range(len(a[0])):
            if a[i][j] >= 0:
                totalCost += cost[a[i][j]]
    return totalCost
h, w = [int(i) for i in input().split()]
c = [[0 for _ in range(10)] for _ in range(10)]
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(10):
    c[i] = [int(i) for i in input().split()]
for i in range(h):
    a[i] = [int(i) for i in input().split()]
print(func(h, w, c, a))
"""
print(func(2, 4, [[0, 9, 9, 9, 9, 9, 9, 9, 9, 9], [9, 0, 9, 9, 9, 9, 9, 9, 9, 9], [9, 9, 0, 9, 9, 9, 9, 9, 9, 9],
                  [9, 9, 9, 0, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9, 0, 9, 9, 9, 9, 2], [9, 9, 9, 9, 9, 0, 9, 9, 9, 9],
                  [9, 9, 9, 9, 9, 9, 0, 9, 9, 9], [9, 9, 9, 9, 9, 9, 9, 0, 9, 9], [9, 9, 9, 9, 2, 9, 9, 9, 0, 9],
                  [9, 2, 9, 9, 9, 9, 9, 9, 9, 0]], [[-1, -1, -1, -1], [8, 1, 1, 8]]))
print(func(5, 5, [[0, 999, 999, 999, 999, 999, 999, 999, 999, 999], [999, 0, 999, 999, 999, 999, 999, 999, 999, 999],
                  [999, 999, 0, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 0, 999, 999, 999, 999, 999, 999],
                  [999, 999, 999, 999, 0, 999, 999, 999, 999, 999], [999, 999, 999, 999, 999, 0, 999, 999, 999, 999],
                  [999, 999, 999, 999, 999, 999, 0, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 0, 999, 999],
                  [999, 999, 999, 999, 999, 999, 999, 999, 0, 999], [999, 999, 999, 999, 999, 999, 999, 999, 999, 0]],
           [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]))
print(func(3, 5, [[0, 4, 3, 6, 2, 7, 2, 5, 3, 3], [4, 0, 5, 3, 7, 5, 3, 7, 2, 7], [5, 7, 0, 7, 2, 9, 3, 2, 9, 1],
                  [3, 6, 2, 0, 2, 4, 6, 4, 2, 3], [3, 5, 7, 4, 0, 6, 9, 7, 6, 7], [9, 8, 5, 2, 2, 0, 4, 7, 6, 5],
                  [5, 4, 6, 3, 2, 3, 0, 5, 4, 3], [3, 6, 2, 3, 4, 2, 4, 0, 8, 9], [4, 6, 5, 4, 3, 5, 3, 2, 0, 8],
                  [2, 1, 3, 4, 5, 7, 8, 6, 4, 0]], [[3, 5, 2, 6, 1], [2, 5, 3, 2, 1], [6, 9, 2, 5, 6]]))
"""

Solution (Python):
H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
A = [list(map(int,input().split())) for _ in range(H)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k]+C[k][j])

c = [0]*10
for h in range(H):
    for w in range(W):
        if A[h][w] >= 0:
            c[A[h][w]] += 1

ans = 0
for i in range(10):
    ans += C[i][1]*c[i]

print(ans)

Solution (Python):
h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
a = [list(map(int, input().split())) for _ in range(h)]

for x in range(10):
    for y in range(10):
        for z in range(10):
            c[y][z] = min(c[y][z], c[y][x] + c[x][z])

ans = 0
for x in range(h):
    for y in range(w):
        if a[x][y] >= 0:
            ans += c[a[x][y]][1]

print(ans)

Solution (Python):


from scipy.sparse.csgraph import floyd_warshall

H, W = map(int, input().split())
C = [None] * 10
for i in range(10):
    C[i] = list(map(int, input().split()))
field = [None] * H
for i in range(H):
    field[i] = list(map(int, input().split()))


dist = floyd_warshall(C)

ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j] != -1:
            
            ans += dist[field[i][j]][1]
print(int(ans))

Solution (Python):


H, W = map(int, input().split())
C = [None] * 10
for i in range(10):
    C[i] = list(map(int, input().split()))
field = [None] * H
for i in range(H):
    field[i] = list(map(int, input().split()))


for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])

ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j] != -1:
            
            ans += C[field[i][j]][1]
print(ans)

Solution (Python):


from scipy.sparse.csgraph import dijkstra

H, W = map(int, input().split())
C = [None] * 10
for i in range(10):
    C[i] = list(map(int, input().split()))
field = [None] * H
for i in range(H):
    field[i] = list(map(int, input().split()))


dist = dijkstra(C)

ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j] != -1:
            
            ans += dist[field[i][j]][1]
print(int(ans))

Solution (Python):
H,W=map(int,input().split())
N=10
c=[[int(i) for i in input().split()] for i in range(N)]
A=[[int(i) for i in input().split()] for i in range(H)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if c[i][k]+c[k][j]<c[i][j]:
                c[i][j]=c[i][k]+c[k][j]
ans=0
for i in range(H):
    for j in range(W):
        if A[i][j]==-1:
            continue
        ans+=c[A[i][j]][1]
print(ans)