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 sys

def warshall_floyd():
    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])

H, W = map(int, input().split())
inf = float("inf")
C = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(10)]
A = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(H)]
warshall_floyd()
res = 0
for row in A:
    for col in row:
        if col != -1:
            res += C[col][1]

print(res)

Solution (Python):

import copy
from itertools import product
import sys

sys.setrecursionlimit(10**6)

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

min_ = [[10**4]*10 for i in range(10)]











def dfs(start=0, now=0, value=0):
    for i in range(10):
        value_tmp = value+map_[now][i]
        if value_tmp < min_[start][i]:
            min_[start][i] = value_tmp
            dfs(start, now=i, value=value_tmp)


for i in range(10):
    dfs(start=i, now=i, value=0)

count = [0]*10
for i in range(h):
    tmp = list(map(int, input().split()))
    for i in tmp:
        if i != -1:
            count[i] += 1

ans = 0
for i in range(10):
    ans += min_[i][1]*count[i]
print(ans)

Solution (Python):
H,W = map(int,input().split())
Cls = []
for i in range(10):
    Cls.append(list(map(int,input().split())))
for k in range(10):
    for i in range(10):
        for j in range(10):
            Cls[i][j] = min(Cls[i][j], Cls[i][k] + Cls[k][j])
costls = []
for i in range(10):
    costls.append(Cls[i][1])
numls = []
for i in range(H):
    numls += list(map(int,input().split()))
ans = 0
for i in range(H*W):
    if numls[i] == -1:
        continue
    ans += costls[numls[i]]
print(ans)

Solution (Python):
from heapq import heappop, heappush
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


class Dijkstra:
    """Graph input:
    {
    node:{node:cost,node:cost...},
    node:{node:cost,node:cost...},
    ...
    }
    """

    def __init__(self, graph: dict, N: int):
        self.graph = graph
        self.costs = [float("inf")] * N

    def calculate(self, start):
        queue = list()

        
        self.costs[start] = 0
        heappush(queue, (0, start))  

        while queue:
            
            cost_from_start, min_node = heappop(queue)

            
            for link, cost in self.graph[min_node].items():
                if cost_from_start + cost < self.costs[link]:
                    self.costs[link] = cost_from_start + cost
                    heappush(queue, (self.costs[link], link))

        return self.costs


def main():
    h, w = input_int_list()

    G = defaultdict(dict)
    for i in range(10):
        line = input_int_list()
        for j in range(10):
            G[j][i] = line[j]

    
    dijkstra = Dijkstra(G, 10)
    costs = dijkstra.calculate(1)

    cnts = defaultdict(int)
    for _ in range(h):
        line = input_int_list()
        for n in line:
            cnts[n] += 1

    ans = 0
    for k, v in cnts.items():
        if k == -1 or k == 1:
            continue
        ans += costs[k] * v

    print(ans)
    return


if __name__ == "__main__":
    main()

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



from math import gcd
from itertools import combinations,permutations,accumulate, product 

from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq














import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7


INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
class WarshallFloyd(object):
    def __init__(self):
        self.max_v = 10
        self.min_dist = [readInts() for _ in range(10)]
    def compute(self):
        for k,i,j in product(range(self.max_v), repeat = 3):
            
            self.min_dist[i][j] = min(self.min_dist[i][j], self.min_dist[i][k] + self.min_dist[k][j])
    def solve(self, n):
        if n == 1:
            return 0
        else:
            return self.min_dist[n][1]
h,w = readInts()
w = WarshallFloyd()
w.compute()
ans = 0
A = [readInts() for _ in range(h)]
for a in A:
    for i in a:
        if i == -1:
            continue
        ans += w.solve(i)
print(ans)

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


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 

d=warshall_floyd(C, 10)

ans=0
for _ in range(H):
	A=list(map(int, input().split()))
	for a in A:
		if a==-1:
			continue
		else:
			ans+=d[a][1]

print(ans)

Solution (Python):

import collections as cl
import sys


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 main():
    H, W = MI()
    costs = []

    for i in range(10):
        cost_row = LI()
        costs.append(cost_row)

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

    ans = 0
    for _ in range(H):
        row = LI()
        for item in row:
            if item == -1:
                continue
            ans += costs[item][1]

    print(ans)


main()

Solution (Python):
import sys
import queue
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def ccc(start, goal, mat):
	open=queue.PriorityQueue()
	close=set()
	open.put((0, start))
	
	while True:
		cost, pos = open.get()
		
		if pos == 1:
			return cost
		if pos in close:
			continue
		for i in range(0,9+1):
			if i == pos:
				continue
			open.put((cost + mat[pos][i], i))
		else:
			close.add(pos)
	
	return -1

def main():
	
	h, w = tin()
	
	mm = [lin() for _ in range(10)]
	dist=dict()
	for i in range(0, 9+1):
		dist[i] = ccc(i,1,mm)
	dist[-1]=0
	
	ret=0
	for hi in range(h):
		al = lin()
		for v in al:
			ret += dist[v]
	return ret
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
H,W=map(int,input().split())
numbers=[list(map(int,input().split())) for _ in range(10)]
A=[list(map(int,input().split())) for _ in range(H)]
cost=[[1001 for _ in range(10)] for _ in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            cost[i][j] = min(cost[i][j] , numbers[i][j] , numbers[i][k] + numbers[k][j] ,
                             cost[i][k] + cost[k][j] , numbers[i][k] + cost[k][j],
                             numbers[i][k] + cost[k][j])
ans=0
for a in A:
    for a_ in a:
        if a_ == 1 or a_ == -1:
            pass
        else:
            ans+=cost[a_][1]
print(ans)

Solution (Python):
def main():
	H, W = [int(x) for x in input().split(" ")]
	C = []
	for i in range(10):
		c = [int(m) for m in input().split(" ")]
		C.append(c)
	A = [0] * 10 
	for i in range(H):
		a = [int(m) for m in input().split(" ")]
		for j in range(W):
			if a[j] != -1:
				A[a[j]] += 1

	MP = [[C[i][1] for i in range(10)]] 
	for i in range(9):
		MP.append([min([(C[k][j] + MP[-1][j]) for j in range(10)]) for k in range(10)])

	minMP = [10000] * 10
	for i in range(len(MP)):
		for j in range(len(MP[i])):
			minMP[j] = min([minMP[j], MP[i][j]])
	print(sum([p * q for (p, q) in zip(A, minMP)]))

main()

Solution (Python):
h,w = map(int,input().split())
dist = [[float("inf")] * 10 for _ in range(10)]
for i in range(10):
  cost = list(map(int,input().split()))
  for j in range(10):
    dist[i][j] = cost[j]
wall = []
for _ in range(h):
  wall.append(list(map(int,input().split())))
V = 10
for k in range(V):
  for i in range(V):
    for j in range(V):
      if dist[i][k]!=float("inf") and dist[k][j]!=float("inf"):
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 0
for wa in wall:
  for wi in wa:
    if wi != -1:
      ans += dist[wi][1]
print(ans)

Solution (Python):
from collections import Counter
from scipy.sparse.csgraph import floyd_warshall

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


num_counter = Counter()
for i in range(H):
    num_counter += Counter(A[i])

if -1 in num_counter:
    del num_counter[-1]

if 1 in num_counter:
    del num_counter[1]

nei_graph = floyd_warshall(C, directed=True)

ans = 0
for k, v in num_counter.items():
    ans += nei_graph[k][1] * v

print(int(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])

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

print(answer)

Solution (Python):



INF = (2*10**7)*100 + 1234567 

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


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] and c[i][k]!=INF and c[k][j]!=INF:
                c[i][j] = c[i][k] + c[k][j]

ans = 0
for i in range(H):
    A_row = [int(e) for e in input().split()]
    for A in A_row:
        if A != -1:
            ans += c[A][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):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  


H, W = na()
c = [na() for _ in range(10)]
A = [na() for _ in range(H)]
adj = [[] for _ in range(10)]

c = np.array(c)
d = shortest_path(c)
ans = 0
for y in range(H):
    for x in range(W):
        if A[y][x] != -1:
            
            ans += d[A[y][x]][1]
print(int(ans))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  


H, W = na()
c = [na() for _ in range(10)]
A = [na() for _ in range(H)]
adj = [[] for _ 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])
ans = 0
for y in range(H):
    for x in range(W):
        if A[y][x] != -1:
            
            ans += c[A[y][x]][1]
print(ans)

Solution (Python):
from networkx import *
h,w=map(int,input().split());r=range(10);G=DiGraph();G.add_nodes_from(r);C=[[*map(int,input().split())]for _ in r];G.add_weighted_edges_from([(i,j,C[i][j])for i in r for j in r]);S=[single_source_dijkstra_path_length(G,i)[1]for i in r];A=[[*map(int,input().split())]for _ in "_"*h];print(sum(S[abs(x)] for a in A for x in a))

Solution (Python):
from networkx import *
h,w=map(int,input().split())
G=DiGraph()
G.add_nodes_from(range(10))
C=[[*map(int,input().split())]for _ in "_"*10]
G.add_weighted_edges_from([(i,j,C[i][j])for i in range(10)for j in range(10)])
S=[single_source_dijkstra_path_length(G,i)[1]for i in range(10)]
A=[[*map(int,input().split())]for _ in "_"*h]
print(sum(S[abs(x)] for a in A for x in a))

Solution (Python):
import heapq
H,W = map(int, input().split())
C = []
for i in range(10):
    C.append(list(map(int, input().split())))
INF = float("inf")

def dfs(x):
    memo = [INF]*10
    memo[x] = 0
    hq = [(0,x)]
    heapq.heapify(hq)
    while hq:
        cost,step = heapq.heappop(hq)
        if cost > memo[step]:
            continue
        for j,c in enumerate(C[step]):
            if memo[j] > memo[step] + c:
                memo[j] = memo[step] + c
                heapq.heappush(hq,(memo[j],j))
    return memo[1]

A = [0]*10
for h in range(H):
    for w in map(int, input().split()):
        if w == -1:
            continue
        else:
            A[w] += 1
ans = 0
for number, a in enumerate(A):
    ans += a*dfs(number)
print(ans)

Solution (Python):
from collections import Counter
from itertools import product

def main():
    with open(0) as f:
        H, W = map(int, f.readline().split())
        C = [list(map(int, f.readline().split())) for _ in range(10)] 
        A = Counter(map(int, f.read().split()))

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

    ans = sum(C[key][1]*value for key,value in A.items() if key != -1)
    print(ans)

main()

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

ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] != -1:
            ans += cost[A[h][w]][1]
print(ans)

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

H,W = map(int,readline().split())
C = [None] * 10
for i in range(10):
  C[i] = list(map(int,readline().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):
  line = list(map(int,readline().split()))
  for j in range(len(line)):
    if line[j] == -1:
      continue
    ans += C[line[j]][1]
    
print(ans)

Solution (Python):
h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
num = [0]*10
for _ in range(h):
    a = list(map(int, input().split()))
    for i in a:
        if i == -1:
            continue
        num[i] += 1


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

print(sum(num[x]*c[x][1] for x in range(10)))

Solution (Python):


import sys

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

A = []
for h in range(H):
    a = list(map(int, sys.stdin.readline().strip().split()))
    A.append(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])


cost = [c[1] for c in C]


ans = 0
for h in range(H):
    for w in range(W):
        
        if A[h][w] == -1:
            continue
        ans += cost[A[h][w]]

print(ans)

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
h,w = map(int,input().split())
g = Graph()
for i in range(10):
    c = list(map(int,input().split()))
    for j in range(10):
        src,dst,weight = i,j,c[j]
        g.add_edge(src, dst, weight)

ans = 0
for y in range(h):
    tmp = list(map(int,input().split()))
    for x in range(w):
        if tmp[x] != -1 and tmp[x] != 1:
            d = Dijkstra(g, tmp[x])
            ans += d.shortest_distance(1)
print(ans)

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            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 wall[i][j]!=-1:
            ans += dist[wall[i][j]][1]
print(ans)

Solution (Python):
H,W=map(int,input().split())
C=[list(map(int,input().split())) for _ in range(10)]
d=[0]*10
for _ in range(H):
  for i in list(map(int,input().split())):
    if i>=0: d[i]+=1
r=range(10)
for k in r:
  for i in r:
    for j in r:
      C[i][j]=min(C[i][j],C[i][k]+C[k][j])

print(sum(C[i][1]*d[i] for i in r))

Solution (Python):
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

H,W=mint()
c=[lint() for _ in range(10)]
A=[lint() for _ in range(H)]
cost=[INF]*10
cost[1]=0
h=[(0,1)]
heapify(h)
while h:
    d,i=heappop(h)
    if d>cost[i]:
        continue
    for j in range(10):
        tmp=c[j][i]+d
        if tmp<cost[j]:
            cost[j]=tmp
            heappush(h,(tmp,j))
ans=0
for i,j in product(range(H),range(W)):
    if A[i][j]>=0:
        ans+=cost[A[i][j]]
print(ans)

Solution (Python):
import heapq
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)]
flag = [[1 for _ in range(10)] for _ in range(10)]
for i in range(10):
    que = [[0, i]]
    while que:
        now = heapq.heappop(que)
        flag[i][now[1]] = 0
        for j in range(10):
            if flag[i][j]:
                heapq.heappush(que, [c[i][now[1]]+ c[now[1]][j], j])
                if c[i][now[1]]+c[now[1]][j] < c[i][j]:
                    c[i][j] = c[i][now[1]]+ c[now[1]][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):
import math
import fractions



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''









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

cost = []

for i in range(10):
    cost.append(list(map(int, input().split())))



INF = 1e9
costs = [[INF for i in range(10)] for j in range(10)]

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


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

for i in range(h):
    row = list(map(int, input().split()))
    for k in row:
        if(k!=-1): needs[k]+=1

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

print(ans)

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

dist = []
for n in range(N):
    dist.append(list(map(int,input().split())))
dist=[list(x) for x in zip(*dist)]

from collections import deque
start = 1

color = {}
for n in range(N):
    color[n] = -1
    
cost = {}
for n in range(N):
    cost[n] = 10**10
    
parent = {}
for n in range(N):
    parent[n] = -1

cost[start] = 0
S = deque([])
while True:
    mincost = 10**10
    for n in range(N):
        if color[n] != 1 and cost[n] < mincost:
            mincost = cost[n]
            start = n
    
    if mincost == 10**10:
        break
    
    color[start] = 1
    
    for n in range(N):
        if color[n] != 1 and dist[start][n] != -1:
            if cost[start] + dist[start][n] < cost[n]:
                cost[n] = cost[start] + dist[start][n]
                parent[n] = start
                color[n] = 0

cost[-1]=0
ans=0
for h in range(H):
    W = list(map(int,input().split()))
    for w in W:
        ans += cost[w]
print(ans)

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

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

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



ans = 0
for i in Aarray:
    for j in i:
        if(j != -1):
            ans += cArray[j][1]

print(ans)

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

visited = {}
dist = {}
for i in range(10):
    dist[i] = 100000
dist[1] = 0

while len(dist) > 0:
    cur, curDist = sorted(dist.items(), key=lambda x: x[1])[0]
    del dist[cur]
    visited[cur] = curDist

    for i in range(10):
        if i == cur or i in visited:
            continue

        newDist = curDist + c[i][cur]
        dist[i] = min(dist[i], newDist)

cnts = [0] * 10
for _ in range(h):
    a = list(map(int, input().split()))
    for ai in a:
        if ai != -1:
            cnts[ai] += 1

cnt = 0
for i in range(10):
    cnt += cnts[i]*visited[i]

print(cnt)

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

cost = [99999]*10
cost[1] = 0

def f(n):
    for i in range(10):
        flag = False
        cc = C[i][n]+cost[n]
        if cc < cost[i]:
            flag = True
            cost[i] = cc
            f(i)

f(1)

ans = 0
for _ in range(H):
    for n in map(int, input().split()):
        if n < 0:
            continue
        ans += cost[n]

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 k in range(10):
        for l in range(10):
            C[k][l] = min(C[k][l], C[k][i]+C[i][l])
ans = 0
"""
for _ in C:
    print(_)
"""
for i in range(H):
    A = list(map(int,input().split()))
    for j in A:
        if j != -1:
            ans += C[j][1]
print(ans)

Solution (Python):
h,w = map(int,input().split())
c = []
for i in range(10):
  ci = list(map(int,input().split()))
  c.append(ci)
x = [0 for _ in range(10)]
for _ in range(h):
  a = list(map(int,input().split()))
  for ai in a:
    if ai != -1:
      x[ai] += 1
d = [float("inf") for _ in range(10)]
d[1] = 0
done = [False for _ in range(10)]
while sum(done) < 10:
  mni = -1
  mn = float("inf")
  for i in range(10):
    if done[i] == False:
      if mn > d[i]:
        mn = d[i]
        mni = i
  done[mni] = True
  for i in range(10):
    if done[i] == False:
      d[i] = min(d[i],d[mni]+c[i][mni])
ans = 0
for i in range(10):
  ans += x[i]*d[i]
print(ans)