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):
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        
        
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.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)]

graph = WarshallFloyd(10)
for i in range(10):
    for j in range(10):
        graph.add(i, j, C[i][j], directed=True)

d = graph.WarshallFloyd_search()

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

print(ans)

Solution (Python):
import numpy as np
import heapq



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

cost = np.zeros((10,10),dtype=np.int64)
for i in range(10):
  temp = map(int,input().split())
  for j,x in enumerate(temp):
    cost[j,i] = x

d = np.zeros(10,dtype=np.int64)

h = []
heapq.heappush(h,(0,1))
while h:
  dx,x = heapq.heappop(h)
  for y in range(10):
    if y in [1,x]:
      continue
    if d[y] == 0 or dx + cost[x,y] < d[y]:
      d[y] = dx+cost[x,y]
      heapq.heappush(h,(d[y],y))

answer = 0
for _ in range(H):
  row = input().split()
  for x in row:
    x = int(x)
    answer += 0 if x == -1 else d[x]
    
print(answer)

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]

n = [0]*10
for row in A:
    for a in row:
        if a != -1:
            n[a] += 1
n[1] = 0

def get_cost(n,tmp_cost = None):
    if cost[n] != None:
        return cost[n]
    if tmp_cost == None:
        tmp_cost = c[n][1]
    ret = tmp_cost
    for i in range(10):
        if i == n:
            continue
        if c[n][i] < tmp_cost:
            ret = min(ret,get_cost(i,tmp_cost-c[n][i])+c[n][i])
    if ret < tmp_cost:
        cost[n] = ret
    return ret

cost = [None]*10
cost[1] = 0
ans = 0
for i,ni in enumerate(n):
    if ni > 0:
        ans += ni * get_cost(i)
print(ans)

Solution (Python):
H,W=map(int,input().split())
C=[]
for i in range(10):
    c=list(map(int,input().split()))
    C.append(c)
decide=set()
INF=10**9
cost=[INF]*10
def check(cost):
    for i in cost:
        if i==INF:
            return True
    return False
while(check(cost)):
    l=-1
    m=INF
    for j in range(10):
        for i in range(10):
            if i in decide:
                continue
            c=min(C[i][1],C[i][j]+cost[j])
            if c<m:
                m=c
                l=i
    cost[l]=m
    decide.add(l)
ans=0
for i in range(H):
    A=list(map(int,input().split()))
    for j in A:
        if j==-1:
            continue
        ans+=cost[j]
print(ans)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall as wf
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)]
C = wf(C)
cost = 0
for y in range(h):
    for x in range(w):
        if A[y][x] != -1:
            cost += C[A[y][x]][1]
print(int(cost))

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)]
INF = float('inf')
cost = 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 y in range(h):
    for x in range(w):
        if A[y][x] != -1:
            cost += C[A[y][x]][1]
print(cost)

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


n=10
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

d=warshall_floyd(c)
ans=0

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

print(ans)

Solution (Python):

import sys
import heapq
import copy
import itertools

inf = float('inf')

class Graph_dijkstra(object):
    def __init__(self, V: "List[int]", E: "Set[Tuple[int, int]]", L: "Dict[Tuple[int, int], int]"):
        self.V = V
        self.E = E
        self.L = L
        self.adjacent = self.init_adjacent() 
        self.shortest_path = self.init_shortest_path() 
    
    def init_adjacent(self):
        ret = {v: [] for v in self.V}
        for e in self.E:
            ret[e[0]].append(e[1])
        return ret
    
    def init_shortest_path(self):
        ret = {(s, g): inf for s, g in itertools.permutations(self.V, 2)}
        for v in self.V:
            ret[(v, v)] = 0
        return ret
    
    def dijkstra(self, s: int):
        D = {v: inf for v in self.V}
        D[s] = 0
        prev = {v: None for v in self.V}
        Q = [(0, s)]

        while len(Q) > 0:
            du, u = heapq.heappop(Q)
            for v in self.adjacent[u]:
                e = (u, v)
                alt = du + self.L[e]
                if alt < D[v]:
                    D[v] = alt
                    prev[v] = u
                    heapq.heappush(Q, (D[v], v))

        for v in self.V:
            self.shortest_path[(s, v)] = D[v]

    def find_shortest_path(self, s: int, g:int):
        d = self.shortest_path[(s, g)]
        if d < inf:
            return d
        self.dijkstra(s)
        return self.shortest_path[(s, g)]


def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    V = list(range(10))
    E = set()
    L = dict()

    for i in range(10):
        for j in range(10):
            e = (i, j)
            E.add(e)
            L[e] = c[i][j]
    
    G = Graph_dijkstra(V, E, L)

    count = [0 for _ in range(10)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == -1:
                continue
            count[A[h][w]] += 1
    
    total = 0
    for i in range(10):
        total += G.find_shortest_path(i, 1) * count[i]

    print(total)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    c = [ [ int(next(tokens)) for _ in range(9-0+1) ] for _ in range(9-0+1) ]  
    A = [ [ int(next(tokens)) for _ in range(W) ] for _ in range(H) ]  
    solve(H, W, c, A)

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 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):
    for j in range(W):
        if A[i][j] == -1 or A[i][j] == 1:
            continue
        else:
            ans += c[A[i][j]][1]

print(ans)

Solution (Python):



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



dist = [[float("inf") for i in range(10)] for i in range(10)] 


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

warshall_floyd(dist)
count=0
for h in range(H):
    for w in range(W):
        a=A[h][w]
        if a != -1:
            count+=dist[A[h][w]][1]
print(count)

Solution (Python):
def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    v_count: 頂点数
    matrix: 隣接行列(到達不能はfloat("inf"))
    """
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


H, W = map(int, input().split())
wall = [list(map(int, input().split()))for _ in range(10)]
mat = warshall_floyd(10, wall)
ans = 0
for i in range(H):
    for n in map(int, input().split()):
        if n == -1:
            continue
        ans += mat[n][1]
print(ans)

Solution (Python):
from functools import reduce
from operator import add
from collections import Counter

H, W = list(map(int, input().split()))
C = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]
A = reduce(add, A)
c = Counter(A)

class WarshallFloyd():
  def __init__(self, matrix):
    self.inf = 1e12
    self.v = len(matrix)
    self.e = matrix
    self.K = [[self.inf]*self.v for _ in range(self.v)]
    self.newK = self.K.copy()
    self.calculated = False
    
  def calc(self):
    for k in range(self.v):
      for i in range(self.v):
        self.newK[i][k] = min([self.K[i][k], self.e[i][k]])
        self.newK[k][i] = min([self.K[k][i], self.e[k][i]])

      for i in range(self.v):
        for j in range(self.v):
          if i!=j and i!=k and j!=k:
            self.newK[i][j] = min([self.K[i][j], self.newK[i][k]+self.newK[k][j]])
      self.K = self.newK.copy()
    self.calculated = True
    return self.K
  
  def shortest_way(self,a,b):
    if not self.calculated:
      self.calc()
    return self.K[a][b]

wf = WarshallFloyd(C)
wf.calc()

answer = 0
for k,v in c.items():
  if k!=-1:
    answer += v * wf.shortest_way(k,1)
print(answer)

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

nums = 10

for k in range(nums):
  for i in range(nums):
    for j in range(nums):
      cost[i][j] = min(cost[i][j],
                       cost[i][k] + cost[k][j])

ans = 0
for wi in wall:
  for wij in wi:
    ans += 0 if wij == -1 else cost[wij][1]
    
print(ans)

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

import numpy as np
inf = 10**3
C = np.full((10,10),inf,dtype = int)
for x in range(10):
    for inp,y in zip(input().split(),range(10)):
        C[x][y] = inp
        
A = [list(map(int,input().split())) for _ in range(h)]

def warshallfloyd(lis):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if i != j and k != i and k != j:
                    C[i][j] = min(C[i][j],C[i][k]+C[k][j])
warshallfloyd(C)
ans = 0
for a in A:
    for aa in a:
        if aa != -1:
            ans += C[aa][1]
print(ans)

Solution (Python):
import collections
import copy

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):
    A += list(map(int,input().split()))
A=[a for a in A if a!=-1 and a!=1]
cnt=collections.Counter(A)

inf=1<<60
best_cost=inf
def walk(place, cost, history):
    global best_cost
    if cost==0:
        best_cost=inf
    if place==1:
        best_cost=min(best_cost,cost)
        return cost
    ret=inf
    for i in range(10):
        if i in history:
            continue
        if i == place:
            continue
        if cost+c[place][i]>=best_cost:
            continue
        history2 = copy.copy(history)
        history2 += [i]
        
        ret=min(ret,walk(i,cost+c[place][i],history+[i]))
    return ret

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

Solution (Python):
from collections import Counter
import heapq
h, w = [int(item) for item in input().split()]
c = [[int(item) for item in input().split()] for _ in range(10)]
a = [[int(item) for item in input().split()] for _ in range(h)]
INF = 10**9

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.num = len(adj)
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def reset(self):
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def calc(self, start, goal=None):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest in range(self.num):
                cost = self.adj[src][dest]
                if cost != INF and self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
                    self.prev[dest] = src
        if goal is not None:
            return self.get_path(goal)
        else:
            return self.dist

    def get_path(self, goal):
        path = [goal]
        dest = goal

        while self.prev[dest] != INF:
            path.append(self.prev[dest])
            dest = self.prev[dest]
        return list(reversed(path))

dijk = Dijkstra(c)
costs = [0] * 10
for i in range(10):
    costs[i] = dijk.calc(i)[1]
    dijk.reset()

count = Counter()
for item in a:
    count.update(item)

ans = 0
for key in count.keys():
    if key >= 0:
        ans += count[key] * costs[key]

print(ans)

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

def getlist():
    return list(map(int, input().split()))

class Graph(object):

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

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

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))

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


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0
        self.prev = defaultdict(lambda: None)

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

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

    def s_d(self, goal):
        return self.dist[goal]

    def s_p(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

H, W = getlist()
c = []
for i in range(10):
    cl = getlist()
    c.append(cl)
A = []
for i in range(H):
    Al = getlist()
    A.append(Al)

g_a = Graph()
for i in range(10):
    for j in range(10):
        a, b, w = i, j, c[i][j]
        if a != b:
            g_a.add_edge(b, a, w)

d_a = Dijkstra(g_a, 1)

ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == -1:
            pass
        else:
            ans += d_a.dist[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])
cnt=[]      
for i in range(10):
    res=0
    for j in range(h):
        res+=A[j].count(i)
    cnt.append(res)    
print(sum(cnt[i]*c[i][1] for i in range(10)))

Solution (Python):

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

c = [[] * 10] * 10

a = [[] * w] * h

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


for z in range(10):
    for y in range(10):
        for x in range(10):
            if c[y][x] > c[y][z] + c[z][x]:
                c[y][x] = c[y][z] + c[z][x]

for y in range(h):
    ax = list(map(int, input().split()))
    a[y] = ax

e = 0
for y in range(h):
    for x in range(w):
        if a[y][x] != -1 and a[y][x] != 1:
            i = a[y][x]
            e += c[i][1]
print(e)

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

Solution (Python):
import collections
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist



h, w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
adj = [[] for _ in range(10)]
for i in range(10):
    for j in range(10):
        c_ = c[i][j]
        adj[i].append((c_, j))
a = []
for i in range(h):
    A = list(map(int, input().split()))
    for j in A:
        a.append(j)
ac = collections.Counter(a)
ans = 0
for i in ac:
    if i != -1:
        ans += dijkstra(adj, 10, i)[1] * ac[i]
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)]
inf = float('inf')
cost = 0
D = [[inf]*10 for i in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            D[i][j] = min(C[i][j],C[i][k]+C[k][j])
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])

for y in range(h):
    for x in range(w):
        if A[y][x] == -1 or A[y][x] == 1:
            continue
        else:
            cost += D[A[y][x]][1]

print(cost)

Solution (Python):
import heapq
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

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

for i in range(10):
    tmp=list(map(int,input().split()))
    for j in range(10):
        if(i!=j):
            G[i].append(edge(j,tmp[j]))
            


ans=[0 for _ in range(10)]
for j in range(N):
    tmp=list(map(int,input().split()))
    for i in tmp:
        if(i!=-1):
            ans[i]+=1


def dijkstra(o):
    d=[float('inf') for i in range(10)]
    d[o]=0
    hq=[]
    prev=[[] for i in range(10)]
    heapq.heappush(hq,(0,o))
    while hq:
        p=heapq.heappop(hq)
        v=p[1]
        if(d[v]<p[0]):
            continue
        for i in G[v]:
            if(d[i.to]>d[v]+i.cost):
                d[i.to]=d[v]+i.cost
                prev[i.to]=prev[v]+[str(sorted([v,i.to]))]
                heapq.heappush(hq,(d[i.to],i.to))
    return d,prev

s=0
for i in range(len(ans)):
    if(ans[i]!=0):
        s+=dijkstra(i)[0][1]*ans[i]
print(s)

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


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])
res=0
for i in range(H):
    for j in range(W):
        if(A[i][j]>=0):
            res+=c[A[i][j]][1]
print(res)

Solution (Python):
H,W=map(int,input().split())
C=[list(map(int,input().split())) for i in range(10)]
cost=[float('inf')]*10
cost[1]=0
check={1,}
while len(check)>0:
    now=check.pop()
    for i in range(10):
        if cost[i]>cost[now]+C[i][now]:
            cost[i]=cost[now]+C[i][now]
            check|={i,}
cost.append(0)
ans=0
for h in range(H):
    for a in map(int,input().split()):
        ans+=cost[a]
print(ans)

Solution (Python):
def main():
    H, W = map(int, input().split())
    g_list = []
    for i in range(10):
        g_list.append(list(map(int, input().split())))
    min_change = [j[1] for j in g_list]
    flag = [0 for _ in range(10)]
    tep = [(j,g) for j, g in enumerate(min_change) if j != 1]  
    min_g = min(tep, key=lambda a:a[1])[0]
    flag[min_g] = 1
    
    while sum(flag) != 9:
        
        for j in range(10):
            if g_list[j][min_g] + min_change[min_g] < min_change[j]:
                min_change[j] = g_list[j][min_g] + min_change[min_g]
        tep = [(k,g) for k, g in enumerate(min_change) if flag[k] == 0 and k != 1]
        if tep != []:
            min_g = min(tep, key=lambda a:a[1])[0]
        else :
            break
        flag[min_g] = 1
    s = 0
    for i in range(H):
        wall = list(map(int, input().split()))
        s += sum([min_change[i] for i in wall if i != -1])
    return s
        
if __name__ == '__main__':
    print(main())

Solution (Python):
h, w = map(int, input().split())
c = []
a = []

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

def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            tmp_cost = glaph[now][i] + cost[now]
            if cost[i] > tmp_cost:
                cost[i] = tmp_cost
                prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return cost[goal]

cost = []
for i in range(10):
    cost.append(search(c, i, 1))
sum = 0
for row in a:
    for element in row:
        if (element != -1):
            sum += cost[element]
print(sum)

Solution (Python):
import numpy as np

minDis = np.zeros((10,10),dtype = int)
minDis.fill(10**18)

edge = np.zeros((10,10),dtype = int)
for i in range(10):
    minDis[i][i] = 0

h,w = map(int,input().split())
mat = np.zeros((h,w),dtype = int)
for i in range(10):
    edge[i] = list(map(int,input().split()))
for i in range(h):
    mat[i] = list(map(int,input().split()))

for start in range(10):
    
    dis = [10**18] *10
    points = set(range(10))
    dis[start] = 0
    
    while points:
        
        md = 10**18+1
        idx = start
        for point in points:
            if dis[point] <md:
                md = dis[point]
                idx = point
        points.remove(idx)
        for neighbour in range(10):
            if neighbour == idx:
                continue
            dis[neighbour] = min(dis[neighbour],dis[idx]+edge[idx][neighbour])
    minDis[start] = dis

res = 0
for i in range(h):
    for j in range(w):
        if mat[i][j] == -1:
            continue
        res += minDis[mat[i][j]][1]
print(res)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall as wf

H,W = map(int,input().split())
C = [[int(i) for i in input().split()] for i in range(10)]
A = [[int(i) for i in input().split()] for i in range(H)]
B = wf(C)
ans = 0

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

print(int(ans))

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
h,w = map(int,input().split())
cost = []
for i in range(10):
  sub = list(map(int,input().split()))
  cost.append(sub)
d = [[float("inf")]*10 for i in range(10)]
L = []
for i in range(10):
    d[i][i] = 0
for i in range(10):
    for j in range(10):
        d[i][j] = cost[i][j]
        d[j][i] = cost[j][i]
d = floyd_warshall(d)
wall = []
for i in range(h):
    cur = list(map(int,input().split()))
    wall.append(cur)
ans = 0
for i in range(h):
    for j in range(w):
        if wall[i][j] != -1:
            ans += d[wall[i][j],1]
print(int(ans))

Solution (Python):
def d_wall(H, W, C, A):
    import scipy.sparse
    
    cost = scipy.sparse.csgraph.floyd_warshall(C)
    
    return int(sum(cost[A[h][w]][1] for h in range(H) for w in range(W) if A[h][w] != -1))

H, W = [int(i) for i in input().split()]
C = [[int(i) for i in input().split()] for j in range(10)]
A = [[int(i) for i in input().split()] for j in range(H)]
print(d_wall(H, W, C, A))

Solution (Python):
h,w=map(int,input().split())
a=[list(map(int,input().split()))for i in range(10)]
b=[list(map(int,input().split()))for i in range(h)]
for h in range(10):
    for i in range(10):
        for j in range(10):
            if a[i][j]>a[i][h]+a[h][j]:
                a[i][j]=a[i][h]+a[h][j]
print(sum([sum([a[d][1] if d>=0 else 0 for d in i])for i in b]))

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

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


sum_cost = 0
for i in range(H):
    num = [int(i) for i in input().split()]
    for n in num:
        if n != -1:
            sum_cost += cost[n][1]

print(sum_cost)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall as wf

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

B = wf(C)

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    return


def B():
    return


def C():
    a,b,c,d = list(map(int, S()))
    s = ["-","+"]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                if eval(str(a)+s[i]+str(b)+s[j]+str(c)+s[k]+str(d)) == 7:
                    print(str(a)+s[i]+str(b)+s[j]+str(c)+s[k]+str(d)+"=7")
                    quit()

def D():
    h,w = LI()
    d = [None for i in range(10)]
    for i in range(10):
        d[i] = LI()
    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):
        s = LI()
        for k in s:
            if k != -1:
                ans += d[k][1]
    print(ans)

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

Solution (Python):
def warshall_floyed(n):
    global d
    for m in range(n):
        for s in range(n):
            for t in range(n):
                d[s][t] = min(d[s][t],
                              d[s][m] + d[m][t])
                
if __name__ == "__main__":
    H,W = map(int, input().split())
    d = [list(map(int, input().split())) for _ in range(10)]
    warshall_floyed(10)
    cnt = [0]*10
    for h in range(H):
        a = list(map(int, input().split()))
        for ai in a:
            if ai>-1:
                cnt[ai]+=1
    ans = 0
    for i in range(10):
        ans += cnt[i]*d[i][1]
    print(ans)