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):
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])
co=[c[i][1] for i in range(10)]
ans=0
for _ in range(h):
	for i in list(map(int,input().split())):
		if i!=-1:ans+=co[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 k in range(10):
    for i in range(10):
        for j in range(10):
            d = C[i][k] + C[k][j]
            if C[i][j] > d:
                C[i][j] = d

cost = [C[d][1] for d in range(10)]

ans = 0
for R in A:
    for a in R:
        if a == -1:
            continue
        ans += cost[a]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



H, W = mi()
C = li2(10)
A = li2(H)


for k in range(10):
    for j in range(10):
        for i 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 abs(A[i][j]) != 1:
            ans += C[A[i][j]][1]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



H, W = mi()
C = li2(10)
A = li2(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 abs(A[i][j]) != 1:
            ans += C[A[i][j]][1]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



H, W = mi()
C = li2(10)
A = li2(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 abs(A[i][j]) != 1:
            ans += C[A[i][j]][1]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



H, W = mi()
C = li2(10)
a = li2(H)
memo = [C[i][1] for i in range(10)]
'''
tmp = -1
def dfs(column, m):
    if column == 1:
        global tmp
        tmp = max(m, tmp)
    for i in range(10):
        if i != column and C[column][i] < m:
            dfs(i, m-C[column][i])
    

for i in range(10):
    if i != 1:
        dfs(i, C[i][1])
        if tmp != -1:
            memo[i] = C[i][1] - tmp
        tmp = -1
'''
INF = 10**9
tmp = 10**9
'''
def dfs(col, m):
    if col == 1:
        global tmp
        tmp = min(m, tmp)
    for i in range(10):
        if i != col and m + C[col][i] < lim:
            dfs(i, m + C[col][i])

for i in range(10):
    if i != 1:
        tmp = INF
        lim = C[i][1]
        dfs(i, 0)
        memo[i] = min(tmp, memo[i])
'''
from collections import deque
for i in range(10):
    que = deque()
    lim = C[i][1]
    for j in range(10):
        if C[i][j] < lim:
            que.append([j, C[i][j]])
    while que != deque():
        
        k = que.popleft()
        for j in range(10):
            if C[k[0]][j] + k[1] < lim and k[0] != j:
                if j == 1:
                    memo[i] = min(memo[i], C[k[0]][j] + k[1])
                else:
                    que.append([j, C[k[0]][j] + k[1]])

ans = 0
for i in range(H):
    for j in range(W):
        if abs(a[i][j]) != 1:
            ans += memo[a[i][j]]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



H, W = mi()
C = li2(10)
a = li2(H)
memo = [C[i][1] for i in range(10)]
'''
tmp = -1
def dfs(column, m):
    if column == 1:
        global tmp
        tmp = max(m, tmp)
    for i in range(10):
        if i != column and C[column][i] < m:
            dfs(i, m-C[column][i])
    

for i in range(10):
    if i != 1:
        dfs(i, C[i][1])
        if tmp != -1:
            memo[i] = C[i][1] - tmp
        tmp = -1
'''
INF = 10**9
tmp = 10**9
'''
def dfs(col, m):
    if col == 1:
        global tmp
        tmp = min(m, tmp)
    for i in range(10):
        if i != col and m + C[col][i] < lim:
            dfs(i, m + C[col][i])

for i in range(10):
    if i != 1:
        tmp = INF
        lim = C[i][1]
        dfs(i, 0)
        memo[i] = min(tmp, memo[i])
'''
from collections import deque
for i in range(10):
    que = deque()
    lim = C[i][1]
    for j in range(10):
        if C[i][j] < lim:
            que.append([j, C[i][j]])
    while que != deque():
        
        k = que.popleft()
        for j in range(10):
            if C[k[0]][j] + k[1] < lim and k[0] != j:
                if j == 1:
                    memo[i] = min(memo[i], C[k[0]][j] + k[1])
                else:
                    que.append([j, C[k[0]][j] + k[1]])

ans = 0
for i in range(H):
    for j in range(W):
        if abs(a[i][j]) != 1:
            ans += memo[a[i][j]]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



H, W = mi()
C = li2(10)
a = li2(H)
memo = [C[i][1] for i in range(10)]
flag = -1
'''
def dfs(column, m):
    if column == 1:
        global flag
        flag = max(m, flag)
    for i in range(10):
        if i!=column and C[column][i] < m:
            dfs(i, m-C[column][i])
    

for i in range(10):
    if i != 1:
        dfs(i, C[i][1])
        if flag != -1:
            memo[i] = C[i][1]-flag
        flag = -1
'''
flag = 10**9

def dfs(col, m):
    if col == 1:
        global flag
        flag = min(m, flag)
    for i in range(10):
        if i != col and m + C[col][i] < lim:
            dfs(i, m + C[col][i])

for i in range(10):
    if i != 1:
        flag = 10**9
        lim = C[i][1]
        dfs(i, 0)
        if flag != 10**9:
            memo[i] = flag

ans = 0
for i in range(H):
    for j in range(W):
        if abs(a[i][j]) != 1:
            ans += memo[a[i][j]]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



H, W = mi()
C = li2(10)
a = li2(H)
memo = [C[i][1] for i in range(10)]
flag = -1
'''
def dfs(column, m):
    if column == 1:
        global flag
        flag = max(m, flag)
    for i in range(10):
        if i!=column and C[column][i] < m:
            dfs(i, m-C[column][i])
    

for i in range(10):
    if i != 1:
        dfs(i, C[i][1])
        if flag != -1:
            memo[i] = C[i][1]-flag
        flag = -1
'''
flag = 10**9

def dfs(col, m):
    if col == 1:
        global flag
        flag = min(m, flag)
    for i in range(10):
        if i != col and m + C[col][i] < lim:
            dfs(i, m + C[col][i])

for i in range(10):
    if i != 1:
        flag = 10**9
        lim = C[i][1]
        dfs(i, 0)
        if flag != 10**9:
            memo[i] = flag

ans = 0
for i in range(H):
    for j in range(W):
        if abs(a[i][j]) != 1:
            ans += memo[a[i][j]]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]


'''
def check(A):
    num = A[1]
    for i in range(10):
        if A[i] >= num and i!=1:
            A[i] = INF
    print('check', A)
    for i in range(10):
        if A[i]!=INF and A[i]!=0 and i!=1:
                return True
    return False


def dfs(A):
    k = check(A)
    while k:
        for i in range(10):
            if i!= 1 and A[i] != INF:
                for j in range(10):
                    if A[j] != INF:
                        A[j] = min(A[i]+C[i][j], A[j])
                        if j == 1 and A[j]==A[i]+C[i][j]:
                            A[i] = INF
        print('dfs', A)
        k = check(A)
    print(A)
    return A[1]

    

H, W = mi()
C = li2(10)
a = li2(H)
ans = 0

INF = 10**9
memo = [INF]*10

for i in range(10):
    if i!= 1:
        A = []
        for j in range(10):
            A.append(C[i][j])
        print(A)
        memo[i] = dfs(A)
        print(i, memo[i])

for i in range(H):
    for j in range(W):
        if a[i][j] != -1 and a[i][j] != 1:
            ans += memo[a[i][j]]

print(memo)

print(ans)
'''
H, W = mi()
C = li2(10)
a = li2(H)
memo = [C[i][1] for i in range(10)]
flag = -1

def dfs(column, m):
    
    if column == 1:
        global flag
        flag = max(m, flag)
    for i in range(10):
        if i!=column and C[column][i] < m:
            dfs(i, m-C[column][i])
    return False

for i in range(10):
    if i != 1:
        dfs(i, C[i][1])
        
        if flag != -1:
            memo[i] = C[i][1]-flag
            
        flag = -1
    

ans = 0

for i in range(H):
    for j in range(W):
        if abs(a[i][j]) != 1:
            ans += memo[a[i][j]]

print(ans)

Solution (Python):
H, W = map(int, input().split())
INF = 10000
G = [[INF] * 10 for _ in range(10)]
for i in range(10):
    G[i][i] = 0

for i in range(10):
    for j, n in enumerate(map(int, input().split())):
        G[i][j] = n

for k in range(10):
    for i in range(10):
        if G[i][k] == INF:
            continue
        for j in range(10):
            if G[k][j] == INF:
                continue
            G[i][j] = min(G[i][j], G[i][k] + G[k][j])

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



magic = [INF] * 10
for i in range(10):
    magic[i] = G[i][1]

ans = 0

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

Solution (Python):
h, w = map(int, input().split())
list_C = [ list(map(int,input().split(" "))) for i in range(10)]
list_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):
            list_C[i][j] = min(list_C[i][j], list_C[i][k]+list_C[k][j])
ans = 0
for i in range(h):
    for j in range(w):
        num = list_A[i][j]
        if num != -1:
            ans += list_C[num][1]
print(ans)

Solution (Python):
def warshall_floyd(G, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

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)]
warshall_floyd(c, 10)
ans = 0
for b in a:
    for i in b:
        if not i == -1:
            ans += c[i][1]
print(ans)

Solution (Python):
H, W = map(int, input().split())
C = [list(map(int, input().split())) for j 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])
 
S = 0
for i in range(H):
    for x in list(map(int, input().split())):
        if x != -1:
            S += C[x][1]
print(S)

Solution (Python):
H, W = map(int, input().split())
C = [list(map(int, input().split())) for j 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])

S = 0
for i in range(H):
    for x in list(map(int, input().split())):
        if x != -1:
            S += C[x][1]
print(S)

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w = na()
c = nan(10)
a = nan(h)

def floyd_warshall(n, dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

def main():
    dist = [[inf] * 10 for _ in range(10)]
    for i in range(10):
        for j in range(10):
            dist[i][j] = c[i][j]
    floyd_warshall(10, dist)
    ans = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == -1:
                continue
            ans += dist[a[i][j]][1]
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappop, heappush
H, W = map(int,input().split())
min_cost = [float("inf")] * 10
min_cost[1] = 0
costs = [list(map(int,input().split())) for _ in range(10)]
que = [(0, 1)]
while que:
    cost, v = heappop(que)
    if cost != min_cost[v]:
        continue
    for to in range(10):
        if min_cost[to] > cost + costs[to][v]:
            min_cost[to] = cost + costs[to][v]
            heappush(que, (min_cost[to], to))
ans = 0
for i in range(H):
    for ch in list(map(int,input().split())):
        if ch != -1:
            ans += min_cost[ch]
print(ans)

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


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

shortest_path = list(zip(*graph))[1]
ans = 0
for _ in range(h):
    for a in map(int, input().split()):
        if a == -1:
            continue
        ans += shortest_path[a]
print(ans)

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

trans_graph = list(zip(*graph))
next_nodes = []
for idx, d in enumerate(trans_graph[1]):
    next_nodes.append((d, idx))
heapq.heapify(next_nodes)

INF = 10**9
decided = [0]*10
decided[1] = 1
dist = [INF]*10
dist[1] = 0

while next_nodes:
    distance, v = heapq.heappop(next_nodes)
    if decided[v]:
        continue
    decided[v] = 1
    dist[v] = distance
    for v2, x in enumerate(trans_graph[v]):
        if decided[v2]:
            continue
        heapq.heappush(next_nodes, (dist[v]+x, v2))

ans = 0
for _ in range(h):
    for x in map(int, input().split()):
        if x == -1:
            continue
        ans += dist[x]

print(ans)

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

trans_graph = list(zip(*graph))
next_nodes = []
for idx, d in enumerate(trans_graph[1]):
    next_nodes.append((d, idx))

heapq.heapify(next_nodes)

INF = 10**9
decided = [0]*10
decided[1] = 1
dist = [INF]*10
dist[1] = 0
while 0 in decided:
    distance, v = heapq.heappop(next_nodes)
    if decided[v]:
        continue
    decided[v] = 1
    dist[v] = distance
    for v2, x in enumerate(trans_graph[v]):
        if decided[v2]:
            continue
        heapq.heappush(next_nodes, (dist[v]+x, v2))

ans = 0
for _ in range(h):
    for x in map(int, input().split()):
        if x == -1:
            continue
        ans += dist[x]

print(ans)

Solution (Python):

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


h,w = map(int,input().split()) 
n=10
d = [list(map(int, input().split())) for i in range(n)]
a= [list(map(int, input().split())) for i in range(h)]

x=warshall_floyd(d)

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

Solution (Python):
from collections import Counter

H, W = map(int, input().split())
graph = [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):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

ctr = Counter(sum(A, []))
ans = 0
for i, c in ctr.items():
    if i == -1:
        continue
    ans += graph[i][1] * c
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)]

DP = [[0] * 10 for _ in range(9)]
for i in range(9):
    for j in range(10):
        if i == 0:
            DP[i][j] = C[j][1]
        else:
            DP[i][j] = min(DP[i - 1][k] + C[j][k] for k in range(10))

answer = 0
for i in range(h):
    for j in range(w):
        if A[i][j] == -1:
            continue
        answer += DP[-1][A[i][j]]

print(answer)

Solution (Python):
def warshall_floyd(c,d):
    
    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])
              if k == 1:
                  d[j] = c[j][k]
    return d

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)]
d_list = [0]*10 
ans = 0
warshall_floyd(c,d_list)

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

Solution (Python):
import copy

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






dp=copy.deepcopy(c)

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])


ans=0
for y in range(H):
    for x in range(W):
        if A[y][x] != -1:
            ans += dp[A[y][x]][1]
print(ans)

Solution (Python):
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
from collections import defaultdict
h, w = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(10)]
dd = defaultdict(int)
for _ in range(h):
    for x in map(int, input().split()):
        if x == -1:
            continue
        dd[x] += 1

trans_table = list(zip(*table))
scores = dijkstra(csgraph_from_dense(trans_table), indices=1)

ans = 0
for k, v in dd.items():
    ans += int(scores[k])*v
print(ans)

Solution (Python):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
from collections import defaultdict
h, w = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(10)]
dd = defaultdict(int)
for _ in range(h):
    for x in map(int, input().split()):
        if x == -1:
            continue
        dd[x] += 1

trans_table = list(zip(*table))
scores = dijkstra(csr_matrix(trans_table), indices=1)
ans = 0
for k, v in dd.items():
    ans += int(scores[k])*v
print(ans)

Solution (Python):
from collections import defaultdict, deque
h, w = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(10)]
dd = defaultdict(int)
for _ in range(h):
    for x in map(int, input().split()):
        if x == -1:
            continue
        dd[x] += 1

INF = 10**9
scores = [INF]*10
decided = [0]*10
queue = deque()
trans_table = list(zip(*table))
for i in range(10):
    x = trans_table[1][i]
    scores[i] = x

MIN = min(set(scores) ^ {0})

while 0 in decided:
    for idx, score in enumerate(scores):
        if score <= MIN:
            decided[idx] = 1

    for i in range(10):
        if i == 1:
            continue
        if decided[i]:
            for j in range(10):
                if not decided[j]:
                    queue.append((i, j))

    while queue:
        i, j = queue.popleft()
        x = trans_table[i][j]
        scores[j] = min(scores[j], scores[i]+x)

    MIN += 1



ans = 0
for k, v in dd.items():
    ans += scores[k]*v
print(ans)

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 = [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])

ct = Counter(chain(*a))
ans = sum(ct[i] * c[i][1] for i in range(10))
print(ans)

Solution (Python):
h,w = map(int,input().split())
cij = [[int(i) for i in input().split()] for j in range(10)]
aij = [[int(i) for i in input().split()] for j in range(h)]








"""
for i in range(10):
	mat[i][i]=0
"""

mat = cij
"""
for i in range(M):
	u,v,l=map(int,input().split())
	mat[u][v] = l
	mat[v][u] = l
"""
for i in range(10):
	for x in range(10):
		for y in range(10):
			mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])

ans = 0

for i in range(h):
    for j in range(w):
        if aij[i][j] != -1 and aij[i][j] != 1:
            
            ans += mat[aij[i][j]][1]

print(ans)

Solution (Python):
[H,W] = [int(s) for s in input().rstrip().split(" ")]
L = []
for num in range(10):
  L.append([int(s) for s in input().rstrip().split(" ")])
for k in range(10):
  for i in range(10):
    for j in range(10):
      L[i][j] = min(L[i][j],L[i][k] + L[k][j])
k = 0
for h in range(H):
  L_h = [int(s) for s in input().rstrip().split(" ")]
  for x in L_h:
    if x != -1:
      k += L[x][1]
print(k)

Solution (Python):
import collections
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)]

result = [0]*10
    
    
def way(n,e,i,p): 
    for j in range(0,10):
        if (n == j):
            continue
        if (n == 1):
            if (e < result[i]):
                result[i] = e
            break
        if (e +  c[n][j] < p):
            q = e + c[n][j]
            way(j,q,i,p)
        
for i in range(0,10):
    result[i] = c[i][1]
    way(i,0,i,result[i])
    

r = []
for w in range(0,10):
    t = 0
    for k in range(0,h):
        l = collections.Counter(a[k])
        t += l[w]
    r.append(t)

ans = 0
for z in range(0,10):
    ans += result[z] * r[z]
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 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 aa in A:
    for a in aa:
        if a >= 0: ans += C[a][1]
print(ans)

Solution (Python):
h,w=map(int,input().split())
tra=[list(map(int,input().split())) for i in range(10)]
ll=[[tra[i][j] for j in range(10)] for i in range(10)]
for i in range(10**3-1):
    for i in range(10):
        for j in range(10):
            if i!=j:
                ll[i][j]=min(ll[i][j],min(ll[i][o]+tra[o][j] for o in range(10) if o!=i and o!=j))
ans=0
for i in range(h):
    for j in map(int,input().split()):
        if j==-1 or j==1:continue
        ans+=ll[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)]
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):

def submit():
    h, w = map(int, input().split())
    costs = [list(map(int, input().split())) for _ in range(10)]
    a = [list(map(int, input().split())) for _ in range(h)]

    
    dist = {(i, j): float('inf') for i in range(10) for j in range(10)}
    for i in range(10):
        for j in range(10):
            dist[(i, j)] = costs[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)])

    ans = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] < 0:
                continue    
            ans += dist[(a[i][j], 1)]
    print(ans)


submit()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w = inpl()
d = [inpl() for _ in range(10)]
a = [inpl() for _ in range(h)]
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])
res = 0
for i in range(h):
    for j in range(w):
        now = a[i][j]
        if now == -1:
            continue
        res += d[now][1]
        
print(res)

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

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

def func(num, goto, ignore):
    if num == goto:
        return 0
    res = []
    for i in range(10):
        if i in ignore:
            continue
        nignore  = deepcopy(ignore)
        nignore.append(i)
        
        plus = func(i, goto, nignore) if d[i][goto] == -1 else d[i][goto]
        
        tmp = c[num][i] + plus
        res.append(tmp)
    return min(res)

h, w = MAP()
c = [LIST() for _ in range(10)]
a = [LIST() for _ in range(h)]
d = [[-1 for _ in range(10)] for _ in range(10)]
for i in range(10): 
    if i == 1:
        continue
    res = func(i, 1, [i])
    d[i][1] = min(c[i][1], res)
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1 or a[i][j] == 1:
            continue
        ans += d[a[i][j]][1]
print(ans)