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):
def dijkstra(s,n,w,cost):
    
    
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d



h,w = map(int, input().split()) 

n=10
w=81

cost = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(10):
    clist = list(map(int, input().split()))
    clist[i]=99999
    
    for j in range(len(clist)):
        if clist[j]!=99999:
            cost[j][i]=clist[j]

costs=dijkstra(1,n,w,cost)
kotae=0
for i in range(h):
    alist = list(map(int, input().split()))
    for al in alist:
        if al!=-1:
            kotae+=costs[al]

print(kotae)

Solution (Python):
import sys
from scipy.sparse.csgraph import floyd_warshall as wf
input = sys.stdin.readline

def main():
  H, W = map(int, input().split())
  link = [list(map(int, input().split())) for i in range(10)]
  a = [list(map(int, input().split())) for i in range(H)]
  
  link = wf(link)
  
  ans = 0
  for i in range(H):
    for j in range(W):
      if a[i][j] != -1:
        ans += link[a[i][j]][1]
  print(int(ans))

if __name__ == "__main__":
  main()

Solution (Python):
h,w=map(int,input().split())
c=[list(map(int,input().split())) for _ in [0]*10]
a=[list(map(int,input().split())) for _ in [0]*h]
cost=[float('inf')]*10
cost[1]=0
for _ in [0]*9:
    for i in range(10):
        cost[i]=min(c[i][j]+cost[j] for j in range(10))
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]>=0:
            ans+=cost[a[i][j]]
print(ans)

Solution (Python):
H, W = map(int, input().split())
D = []
for i in range(10):
  Cs = list(map(int, input().split()))
  D.append(Cs)
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])

r = 0
for i in range(H):
  As = list(map(int, input().split()))
  for j in range(W):
    A = As[j]
    if A < 0:
      continue
    r += D[A][1]
print(r)

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

H,W = [int(x) for x in input().split()]
C = [[int(x) for x in input().split()]for _ in range(10)]
A = [[int(x) for x in input().split()]for _ in range(H)]
cnt = 0
warshall_floyd(C,10)
for line in A:
    for a in line:
        if(a==-1):
            pass
        else:
            cnt += C[a][1]
print(cnt)

Solution (Python):
h,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(10)]
o=[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 l[i][j]>l[i][k]+l[k][j]:
        l[i][j]=l[i][k]+l[k][j]

v=[[l[j][1] if j>=0 else 0 for j in i] for i in o]
print(sum(map(sum,v)))

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


graph = list(zip(*graph))

vst = 1
n = 10
checked = [0] * n
dist = [float('inf')] * n
dist[vst] = 0
for _ in range(n):
    min_dist = float('inf')
    for i in range(n):
        if checked[i] == 0 and dist[i] < min_dist:
            target_v = i
            min_dist = dist[i]
    checked[target_v] = 1
    for to_v in range(n):
        cost = graph[target_v][to_v]
        dist[to_v] = min(dist[target_v] + cost, dist[to_v])



ret = 0
for i in range(h):
    for j in map(int, input().split()):
        if j != -1:
            ret += dist[j]


print(ret)

Solution (Python):
import numpy as np


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


graph = np.transpose(np.array(graph))

vst = 1
n = 10
checked = [0] * n
dist = [float('inf')] * n
dist[vst] = 0
for _ in range(n):
    min_dist = float('inf')
    for i in range(n):
        if checked[i] == 0 and dist[i] < min_dist:
            target_v = i
            min_dist = dist[i]
    checked[target_v] = 1
    for to_v in range(n):
        cost = graph[target_v][to_v]
        dist[to_v] = min(dist[target_v] + cost, dist[to_v])



ret = 0
for i in range(h):
    for j in map(int, input().split()):
        if j != -1:
            ret += dist[j]


print(ret)

Solution (Python):
import numpy as np


def dijkstra(cost_matrix, start_node=0):
    node_num = len(cost_matrix)
    distance = np.full(node_num, np.inf)
    distance[start_node] = 0
    unsearched_nodes = [i for i in range(node_num)]
    while unsearched_nodes:
        min_distance = np.inf
        for each_node in unsearched_nodes:
            if distance[each_node] < min_distance:
                min_distance = distance[each_node]
                target_node = each_node
        unsearched_nodes.remove(target_node)
        each_distance = cost_matrix[target_node]
        for i in range(node_num):
            if each_distance[i] != 0:
                distance[i] = min(distance[i], distance[target_node] + each_distance[i])
    return distance.astype(int)


h, w = map(int, input().split())
graph = np.array([np.array(list(map(int, input().split()))) for _ in range(10)])
graph = np.transpose(graph)
dist = dijkstra(graph, start_node=1)


wall_num = []
for i in range(h):
    wall_num += list(map(int, input().split()))



ret = 0
for num in wall_num:
    if num != -1:
        ret += dist[num]


print(ret)

Solution (Python):
from heapq import heappop, heappush
import numpy as np



def dijkstra(graph, n, vst=0):
    distance = [float('inf')] * n
    distance[vst] = 0
    checked_v = [0] * n
    route = [''] * 10
    route[vst] = str(vst)
    dist = [float('inf')] * n
    dist[vst] = 0
    q = []
    heappush(q, (0, vst))
    for _ in range(n):
        while True:
            min_dist, search_v = heappop(q)
            if checked_v[search_v] == 0:
                break
        checked_v[search_v] = 1
        for to_v in range(n):
            if checked_v[to_v] == 0:
                cost = graph[search_v][to_v]
                if dist[search_v] + cost < dist[to_v]:
                    dist[to_v] = dist[search_v] + cost
                    route[to_v] = route[search_v] + str(to_v)
                    heappush(q, (dist[to_v], to_v))
    return dist


h, w = map(int, input().split())
graph = np.array([np.array(list(map(int, input().split()))) for _ in range(10)])
graph = np.transpose(graph)
dist = dijkstra(graph, 10, vst=1)


wall_num = []
for i in range(h):
    wall_num += list(map(int, input().split()))



ret = 0
for num in wall_num:
    if num != -1:
        ret += dist[num]


print(ret)

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 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())
cost = []
for _ in range(10):
    cost.append(list(map(int, input().split())))
wall = []
for _ in range(H):
    wall.append(list(map(int, input().split())))

dp = [[0 for _ in range(10)] for _ in range(10)]
for i in range(10):
    for j in range(10):
        dp[i][j] = cost[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])

ans = 0
for h in range(H):
    for w in range(W):
        A = wall[h][w]
        if A >= 0:
            ans += dp[A][1]

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

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

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


if __name__ == '__main__':
  main()

Solution (Python):
h, w = map(int, input().split())
d = []
for i in range(10):
    d.append(list(map(int, input().split())))
a = []
for i in range(h):
    a.append(list(map(int, input().split())))
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])







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

Solution (Python):
h, w = map(int, input().split())
d = []
for i in range(10):
    d.append(list(map(int, input().split())))
a = []
for i in range(h):
    a.append(list(map(int, input().split())))
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])







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

Solution (Python):
H, W = map(int, input().split())
C = []
for _ in range(10):
    c = [int(s) for s in input().split()]
    C.append(c)
A = []
for _ in range(H):
    a = [int(s) for s in input().split()]
    for ai in a:
        if ai != -1:
            A.append(ai)
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 = sum([C[ai][1] for ai in A])
print(ans)

Solution (Python):
inf = float("inf")

H, W = map(int, input().split())
C = []
for _ in range(10):
    c = [int(s) for s in input().split()]
    C.append(c)
A = []
for _ in range(H):
    a = [int(s) for s in input().split()]
    for ai in a:
        if ai != -1:
            A.append(ai)
for _ in range(9):
    for i in range(10):
        for j in range(10):
            for k in range(10):
                C[i][j] = min(C[i][j], C[i][k] + C[k][j])
ans = sum([C[ai][1] for ai in A])
print(ans)

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


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


d = warshall_floyd(c)
cnt = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == -1:
            continue
        else:
            cnt += c[A[i][j]][1]
print(cnt)

Solution (Python):
H, W = map(int, input().split())

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

c = [list(map(int, input().split())) for _ in range(10)]
WarshallFloyd(c)

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

ans = 0
for i in A:
    for j in i:
        if j == -1:
            pass
        else:
            ans += c[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)]

INF = 10000

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 h in range(H):
    for w in range(W):
        a = A[h][w]
        if a == -1:
            continue
        ans += C[a][1]
print(ans)

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

cost = [float('inf')]*10
cost[1] = 0
for i in range(10):
    for y in range(10):
        for x in range(10):
            cost[x] = min(cost[x],cost[y]+c[x][y])

A = list(list(map(int,input().split()))for i in range(H))
ans = 0
for a in A:
    for i in a:
        if i != -1:
            ans += cost[i]
print(ans)

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



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

print(ans)

Solution (Python):
H, M = 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
def warshall_floyd(n):
    for i in range(n): 
        for j in range(n): 
            for k in range(n):  
                c[j][k] = min(c[j][k], c[j][i] + c[i][k])

warshall_floyd(10)

for a in A:
    for ai in a:
        if ai == -1: pass
        else:
            ans += c[ai][1]
        
print(ans)

Solution (Python):
def solve(h, w, c, a):
    n = 10
    dp = c.copy()
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    ans = 0
    for i in range(h):
        for j in range(w):
            x = a[i][j]
            if x == -1:
                continue
            ans += dp[x][1]
    return ans

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)]
print(solve(h, w, c, a))

Solution (Python):

h, w = [ int(v) for v in input().split() ]
cost_list = [ [ int(v) for v in input().split() ] for i in range(10) ]


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

ans = 0

for i in range(h):
    line = [ int(v) for v in input().split() ]
    for j in line:
        if j not in [1,-1]:
            ans += cost_list[j][1]

print(ans)

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re



def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 


def create_grid(W, H, value = 0):
    return [[ value for _ in range(H)] for _ in range(W)]


def warshall_floyd(G):
    
    N = len(G)
    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])
    return G

if __name__ == "__main__":
    
    H, W = l_inpl()

    
    G = []
    for i in range(10):
        l = l_inpl()
        G.append(l)

    
    G = warshall_floyd(G)
    l = []
    for _ in range(H):
        li = l_inpl()
        l.extend(li)
    ans = 0

    for i in range(0, 10):
        if i == 1:
            continue
        ans += G[i][1] * l.count(i)
    print(ans)

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

def Warshall_Floyd(d,N=None):
    if N==None : N = len(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])

Warshall_Floyd(C,10)
ans = sum(C[b][1] for a in A for b in a if b!= -1)

print(ans)

Solution (Python):
H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in [0]*10]
A = [list(map(int,input().split())) for _ in [0]*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 = sum(C[b][1] for a in A for b in a if b!= -1)

print(ans)

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


h, w = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(10)]
a = tuple(tuple(map(int, input().split())) for _ in range(h))

cost = warshall_floyd(cost)

ans = 0
for r in range(h):
    for c in range(w):
        frm = a[r][c]
        if frm == -1:
            continue
        ans += cost[frm][1]
print(ans)

Solution (Python):



import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7


h,w = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(10)]
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])
m = [list(map(int,input().split())) for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if m[i][j] == -1:
            continue
        if m[i][j] == 1:
            continue
        else:
            ans += d[m[i][j]][1]
print(ans)

Solution (Python):
from collections import Counter

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

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

count = Counter()
for i in range(H):
    count.update(list(map(int, input().split())))
print(sum([c[i][1] * count[i] for i in range(10)]))

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 i in range(N):
    for j in range(N):
        for k in range(N):
            if c[i][k]+c[k][j]<c[i][j]:
                c[i][j]=c[i][k]+c[k][j]
for i in range(N):
    for j in range(N):
        for k in range(N):
            if c[i][k]+c[k][j]<c[i][j]:
                c[i][j]=c[i][k]+c[k][j]
for i in range(N):
    for j in range(N):
        for k 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)

Solution (Python):
from sys import stdin
from numpy import array
from collections import defaultdict
from heapq import heappush, heappop


def solve(row):
    readline = stdin.readline
    g = defaultdict(list)

    for i in range(10):
        c_i = list(map(int, readline().split()))
        for j in range(10):
            g[i].append((c_i[j], j))

    accm = [0]*10
    for r in range(row):
        a = list(map(int, readline().split()))
        a = array(a)
        for ai in a:
            if ai != -1:
                accm[ai] += 1

    to_1 = []
    for k in range(10):
        from_k = dijkstra(10, g, k)
        to_1.append(from_k[1])

    return sum([to_1[i] * accm[i] for i in range(10)])


def dijkstra(vertex, g, sp):
    d = [float('inf')] * vertex
    d[sp] = 0
    heap = [(d[sp], sp)]

    while heap:
        du, u = heappop(heap)
        for length, v in g[u]:

            if d[v] > du + length:
                d[v] = du + length
                heappush(heap, (d[v], v))
    return d


if __name__ == '__main__':
    row, _ = map(int, input().split())
    print(solve(row))

Solution (Python):
inf=10**17

def tp(a,b):
    return min(a,b,inf)
def tt(a,b):
    return min(a+b,inf)
def tpdot(A,B):
    N=len(A)
    C=[[inf]*N for i in range(N)]
    for i in range(N):
        for j in range(N):
            num=inf
            for k in range(N):
                t=tt(A[i][k],B[k][j])
                num=tp(num,t)
            C[i][j]=num
    return C
def tpeye(N):
    C=[[inf]*N for i in range(N)]
    for i in range(N):
        C[i][i]=0
    return C
def tppower(A,k):
    N=len(A)
    S,T=tpeye(N),A
    x=k
    while x>0:
        if x%2==1:
            S=tpdot(S,T)
        x=x//2
        T=tpdot(T,T)
    return S

H,W=map(int,input().split())
A=[[0]*10 for i in range(10)]
for j in range(10):
    C=[int(i) for i in input().split()]
    for k in range(10):
        A[j][k]=C[k]

A=tppower(A,10)
ans=0
for j in range(H):
    C=[int(i) for i in input().split()]
    for k in range(W):
        if C[k]!=-1:
            ans+=A[C[k]][1]

print(ans)

Solution (Python):
def smaller(x, y):
	if x < y:
		return x
	return y

H, W = map(int, input().split())
C = []
for i in range(0, 10):
	C.append(list(map(int, input().split())))
A = []
for i in range(0, H):
	A.append(list(map(int, input().split())))
magic = []
for i in range(0, 10):
	magic.append(C[i][1])
for i in range(0, 10):
	notvisited = []
	for j in range(0, 10):
		notvisited.append(True)
	notvisited[i] = False
	queue = [[i, notvisited, 0]]
	while queue != []:
		now = queue.pop(0)
		if now[2] < magic[i]:
			if now[0] == 1:
				magic[i] = now[2]
			else:
				for j in range(0, 10):
					if now[1][j] and now[2]+C[now[0]][j] < magic[i]:
						newnotvisit = []
						for k in range(0, 10):
							if j == k:
								newnotvisit.append(False)
							else:
								newnotvisit.append(now[1][k])
						queue.append([j, newnotvisit, now[2]+C[now[0]][j]])
sum = 0
for i in range(0, H):
	for j in range(0, W):
		if A[i][j] != -1:
			sum += magic[A[i][j]]
print(sum)

Solution (Python):
H,W=map(int,input().split())
c=[list(map(int,input().split())) for _ in [0]*10]
a=[list(map(int,input().split())) for _ in [0]*H]
def dp(i,j,l,lim):
    if lim<0:
        return 10**4
    else:
        return min([c[i][j]]+[c[i][k]+dp(k,j,l+[k],lim-c[i][k]) for k in range(10) if k not in l])
cc=[dp(i,1,[i,1],c[i][1]) for i in range(10)]
print(sum([cc[j] for i in a for j in i if j!=-1]))