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):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


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


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



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


def main():
    H, W = MI()
    N = 10
    d = [None for i in range(N)]
    A = [None] * H

    for i in range(N):
        d[i] = LI()

    for i in range(H):
        A[i] = LI()

    d = warshall_floyd(d, N)

    

    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)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")
H, W = map(int, input().split())
graph = np.array([list(map(int, input().split())) for _ in range(10)])

shortest_paths = shortest_path(csr_matrix(graph), method="D")
ans = 0

Alist = [list(map(int, input().split())) for _ in range(H)]
for line in Alist:
    for a in line:
        if a >= 0:
            ans += shortest_paths[a][1]
print(int(ans))

Solution (Python):
import math,itertools,bisect,sys,copy,queue

def LI(): return [int(x) for x in sys.stdin.readline().split()]

H,W = LI()
C = [LI() for _ in range(10)]
A = [LI() 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 x in range(W):
    for y in range(H):
        if A[y][x] >= 0:
            ans += C[A[y][x]][1]
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)
A=[]
for i in range(H):
    a=list(map(int,input().split()))
    A.append(a)

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

print(ans)

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


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

ans = 0
for i in range(h):
  a = [int(x) for x in input().split()]
  for j in range(w):
    if a[j] == -1:
      continue
    else:
      ans += c[a[j]][1]

print(ans)

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

for _ in range(10):
  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 = 0
for i in range(h):
  a = [int(x) for x in input().split()]
  for j in range(w):
    if a[j] == -1:
      continue
    else:
      ans += c[a[j]][1]

print(ans)

Solution (Python):
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
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:
            ans += C[A[i][j]][1]

print(ans)

Solution (Python):

import math
import heapq
import bisect
import numpy as np
from collections import Counter


INF = 10*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)]

N = 100


mp = [[INF]*N for _ in range(11)]
mp[0][1] = 0
for i in range(10):
    mp[i][1] = C[i][1]

for j in range(2,N):
    for i in range(10):
        mp[i][j] = min((C[i][k] + mp[k][j-1]) for k in range(10))

cnt = [0]*10
for a in A:
    for i in range(10):
        cnt[i] += a.count(i)

ans = 0
for i in range(10):
    ans += cnt[i] * mp[i][N-1]

print(ans)

Solution (Python):
INFTY = 10**5
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)]
dist = [[INFTY for _ in range(10)] for _ in range(10)]
for i in range(10):
    dist[i][i] = 0
for i in range(10):
    for j in range(10):
        dist[i][j] = C[i][j]
for k in range(10):
    for i in range(10):
        for j in range(10):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
cnt = 0
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a!=-1:
            cnt += dist[a][1]
print(cnt)

Solution (Python):
INF = 100000

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

dist = [[INF for j in range(10)] for i in range(10)]

for i in range(10):
    for j in range(10):
        dist[i][j] = C[i][j]

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

ans = 0

for al in A:
    for a in al:
        if a != -1:
            ans += dist[a][1]

print(ans)

Solution (Python):
from sys import stdin
H,W = [int(x) for x in stdin.readline().rstrip().split()]
cost = []
for i in range(10):
    cost.append([int(x) for x in stdin.readline().rstrip().split()])

A = []
for i in range(H):
    A.append([int(x) for x in stdin.readline().rstrip().split()])

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 a in A:
    for aa in a:
        if aa == -1:
           continue
        ans += cost[aa][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)]

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
		else:
			ans += C[A[i][j]][1]

print(ans)

Solution (Python):

import sys

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 

def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    min_cost = warshall_floyd(c,10)
    answer = 0

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

            answer += min_cost[A[h][w]][1]
    print(answer)
    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):
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect
from scipy.sparse.csgraph import shortest_path
import numpy as np

MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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 = shortest_path(np.array(c))

ans = 0
for i in range(H):
    for l in range(W):
        if A[i][l] != -1:
            ans += result[A[i][l]][1]
print(int(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 A[i]:
    if j!=1 and j!=(-1):
      ans+=C[j][1]
print(ans)

Solution (Python):
import sys
from pprint import pprint

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])
    has_nagative_cycle = False
    for i in range(n):
        if d[i][i] < 0:
            has_nagative_cycle = True
            break
    for i in range(n):
        d[i][i] = 0
    return has_nagative_cycle

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

walls = [[] for _ in range(H)]
for i in range(H):
	walls[i] = list(map(int, sys.stdin.readline().strip().split()))

warshall_floyd(numbers, 10)


ans = 0
for h in range(H):
	for w in range(W):
		n = walls[h][w]
		ans += 0 if n == -1 or n == 1 else numbers[n][1]
		

print(ans)

Solution (Python):
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
cnt = [0]*11
for _ in range(H):
  for a in map(int, input().split()):
    cnt[a] += 1
D = [[C[i][j] for j in range(10)] for i in range(10)]
k = 0
while k < 10:
  i = 0
  while i < 10:
    j = 0
    while j < 10:
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
      j += 1
    i += 1
  k += 1
print(sum([cnt[i]*D[i][1] for i in range(10)]))

Solution (Python):
def JOI14_B():
    N = I()
    A = [I()for _ in range(N)]
    A.extend(A)
    dp = [[0]*(N*2+1) for _ in range(N*2+1)]

    for j in range(N):
        for i in range(N*2-j):
            if (N-j)%2==1:
                dp[i][i+j] = max(dp[i+1][i+j]+A[i],dp[i][i+j-1]+A[i+j])
            else:
                if A[i]>A[i+j]:
                    dp[i][i+j] = dp[i+1][i+j]
                else:
                    dp[i][i+j] = dp[i][i+j-1]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][i+N-1])
    print(ans)
    
    return

def square869120Contest1_G():
    def held_karp(dists,TL):
        
        """
        Implementation of Held-Karp, an algorithm that solves the Traveling
        Salesman Problem using dynamic programming with memoization.
        Parameters:
            dists: distance matrix
        Returns:
            A tuple, (cost, path).
        """
        n = len(dists)

        
        
        
        C = {}
        dp = defaultdict(int)

        
        for k in range(1, n):
            C[(1 << k, k)] = (dists[0][k], 0)
            dp[(1 << k, k)] = 1

        
        
        for subset_size in range(2, n):
            for subset in itertools.combinations(range(1, n), subset_size):
                
                bits = 0
                for bit in subset:
                    bits |= 1 << bit
                shortest_length = inf
                
                for k in subset:
                    prev = bits & ~(1 << k)

                    res = []
                    for m in subset:
                        if not (prev, m) in C:
                            continue
                        if m == 0 or m == k:
                            continue
                        if C[(prev, m)][0] + dists[m][k]>TL[m][k]:
                            continue
                        res.append((C[(prev, m)][0] + dists[m][k], m))
                        if shortest_length>C[(prev, m)][0] + dists[m][k]:
                            shortest_length = C[(prev, m)][0] + dists[m][k]
                    if not res:
                        continue
                    C[(bits, k)] = min(res)
                    for d,m in res:
                        if shortest_length!=d:
                            continue
                        dp[(bits, k)] += dp[(prev,m)]

        
        bits = (2 ** n - 1) - 1

        
        res = []
        shortest_length = inf
        for k in range(1, n):
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            res.append((C[(bits, k)][0] + dists[k][0], k))
            if shortest_length > C[(bits, k)][0] + dists[k][0]:
                shortest_length = C[(bits, k)][0] + dists[k][0]
        if not res:
            return False
        opt, parent = min(res)
        way = 0
        for d, k in res:
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            if shortest_length < d:
                continue
            way += dp[(bits,k)]

        
        path = []
        for i in range(n - 1):
            path.append(parent)
            new_bits = bits & ~(1 << parent)
            _, parent = C[(bits, parent)]
            bits = new_bits

        
        path.append(0)

        return shortest_length, list(reversed(path)), way

    N, M = LI()
    dist = [[inf]*N for _ in range(N)]
    TL = [[0]*N for _ in range(N)]
    for _ in range(M):
        s, t, d, time = LI()
        s -= 1; t -= 1
        dist[s][t] = dist[t][s] = d
        TL[s][t] = TL[t][s] = time
    ans = held_karp(dist,TL)
    if (not ans) or ans[2]==0:
        print("IMPOSSIBLE")
        return
    print(ans[0],ans[2])
    return

def JOI13_D():
    def solve(yday,leader,next):
        a = [0]*3
        for i in range(3):
            if next&(1<<i)==(1<<i):
                a[i] = 1
        rep = 0
        if a[leader]==0:
            return rep
        for i in range(3):
            if yday&(1<<i)==(1<<i):
                if a[i]==1:
                    rep = 1
        return rep
    N = I()
    S = SI()
    member = {"J":0,"O":1,"I":2}
    dp = [[0]*8 for _ in range(N+1)]
    dp[0][1] = 1
    for i in range(N):
        leader = member[S[i]]
        for j in range(8):
            for k in range(8):
                dp[i+1][j] += (dp[i][k]*solve(k,leader,j))
    ans = sum(dp[-1])%10007
    
    print(ans)
    return

def JOI16_D():
    N, M = LI()
    A = [(I()-1)for _ in range(N)]
    imos = [[0] * (N + 1) for _ in range(M)]
    for i in range(M):
        for j in range(N):
            imos[i][j + 1] += imos[i][j] + (A[j] != i)
    cnt = Counter(A)
    dp = [10 ** 9] * (1 << M)
    num = [None] * (1 << M)
    dp[0] = 0
    num[0] = 0
    for b in range(1 << M):
        for i in range(M):
            if b & (1 << i):
                continue
            nb = b | (1 << i)
            if num[nb] is None:
                num[nb] = num[b] + cnt[i]
            l = num[b]
            r = l + cnt[i]
            d = imos[i][r] - imos[i][l]
            dp[nb] = min(dp[nb], dp[b] + d)

    print(dp[-1])
    return

def ABC6_D():
    N = I()
    C = [I() for _ in range(N)]
    LIS = [C[0]]
    for i in range(N):
        if C[i] > LIS[-1]:
            LIS.append(C[i])
        else:
            LIS[bisect.bisect_left(LIS, C[i])] = C[i]
    print(N - len(LIS))
    return

def ABC134_E():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(A[0])
    L = 1
    for i in range(1,N):
        cur = bisect.bisect_left(que,A[i])
        
        if cur==0:
            que.appendleft(A[i])
            L += 1
        else:
            que[cur-1] = A[i]

    
    ans = len(que)
    print(ans)

    return

def JOI7_F():
    def dijkstra_2(edge_adj, node, start):
        
        
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    V = [[inf]*N for _ in range(N)]
    ans = []
    for _ in range(K):
        A = LI()
        s = A[1]-1
        t = A[2]-1
        if A[0]==1:
            if V[s][t] <= A[3]:
                continue
            V[s][t] = A[3]
            V[t][s] = A[3]
        else:
            dist = dijkstra_2(V,N,s)
            ans.append(dist[t])
    for v in ans:
        if v==inf:
            print(-1)
            continue
        print(v)
    return

def JOI15_E():
    def bfs(n, E, fordfs):
        
        W = [inf] * n
        
        que = deque()
        for e in E:
            e -=1
            W[e] = 0
            que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] > nowW + 1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    class Dijkstra(object):
        """
        construct: O(ElogV)
        """

        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, M, K, S = LI()
    P, Q = LI()
    C = [I()for _ in range(K)]
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t = LI()
        s -= 1
        t -= 1
        V[s].append(t)
        V[t].append(s)
    L = bfs(N,C,V)
    
    cost = [[]for _ in range(N)]
    for i in range(N):
        for v in V[i]:
            if L[v]==0:
                continue
            elif L[v]<=S:
                cost[i].append((v,Q))
            else:
                cost[i].append((v,P))
    di = Dijkstra(cost)
    ans = di.dist
    
    if L[-1]<=S:
        print(ans[N-1]-Q)
    else:
        print(ans[N-1]-P)
    return

def JOI13_E():
    def bfs(n, e, fordfs):
        
        W = [inf] * n
        
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == inf:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    def dijkstra_2(edge_adj, node, start):
        
        
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    C = [[]for _ in range(N)]
    V = [[]for _ in range(N)]
    for i in range(N):
        C[i] = LI()
    for i in range(K):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    costV = [[inf]*N for _ in range(N)]
    for i in range(N):
        L = bfs(N,i,V)
        c = C[i][0]; l = C[i][1]
        for j in range(N):
            if i==j:
                continue
            if L[j]<=l:
                costV[i][j] = c
    dist = dijkstra_2(costV,N,0)
    ans = dist[N-1]
    
    print(ans)
    return

def ABC12_D():
    def warshall_floyd(n, d):
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    N, M = LI()
    V = [[inf]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for _ in range(M):
        a, b, t = LI()
        a -= 1
        b -= 1
        V[a][b] = t
        V[b][a] = t
    L = warshall_floyd(N,V)
    
    ans = inf
    for i in range(N):
        cur = max(L[i])
        ans = min(ans,cur)
    print(ans)
    return

def ABC79_D():
    def warshall_floyd(n, 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 = LI()
    C = [LI()for _ in range(10)]
    A = [LI()for _ in range(H)]
    L = warshall_floyd(10,C)
    
    ans = 0
    for a in A:
        for i in a:
            if i>=0:
                ans += L[i][1]
    print(ans)
    return



def square869120Contest1_E():
    N, Q = LI()
    A = LI()
    C = LI()
    C.append(1)
    L = [0]*N
    for i in range(1,N):
        L[i] = pow(A[i-1],A[i],mod) + L[i-1]
    
    ans = 0
    now = 0
    for i in range(Q+1):
        next = C[i]-1
        cur = abs(L[next]-L[now])
        ans += cur
        ans %= mod
        now = next
        
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

import gc
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    ABC79_D()
"""

"""

Solution (Python):
H,W=map(int,input().split())
c=[]
for i in range(10):
    tmp=list(map(int,input().split()))
    c.append(tmp)
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):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])

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

Solution (Python):
from scipy.sparse import csr_matrix
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)]

g = csr_matrix(c)
dist = floyd_warshall(g)

ans = 0
for row in a:
    for e in row:
        if e == -1:
            continue

        else:
            ans += dist[e][1]

ans = int(ans)
print(ans)

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

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

ans = 0
for Ai in A:
    for a in Ai:
        if a == -1:
            continue
        ans += c[a][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)]
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])
s=0
for i in range(h):
  for j in range(w):
    if a[i][j]!=-1:
      s+=c[a[i][j]][1]
print(s)

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

H, W = [int(x) for x in input().strip().split()]
C = [0 for _ in range(10)]
for i in range(10):
    C[i] = [int(x) for x in input().strip().split()]

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]
                isChanged = True

ans = 0
for h in range(H):
    W = [int(x) for x in input().strip().split()]
    for w in W:
        if w == -1:
            continue
        ans += C[w][1]

print(ans)

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

H, W = [int(x) for x in input().strip().split()]
C = [0 for _ in range(10)]
for i in range(10):
    C[i] = [int(x) for x in input().strip().split()]

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]
                isChanged = True

ans = 0
for h in range(H):
    W = [int(x) for x in input().strip().split()]
    for w in W:
        if w == -1:
            continue
        ans += C[w][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)]

ans=0

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

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

Solution (Python):
import heapq
import sys

H, W = map(int, input().split())
c = [[int(j) for j in input().split()] for i in range(10)]
A = [[int(j) for j in input().split()] for i in range(H)]
ans = 0
for i in A:
	for j in i:
		if j == -1:
			continue
		a = [(0, j)]
		b = [False] * 10
		d = [sys.maxsize] * 10
		d[j] = 0
		while len(a):
			e = heapq.heappop(a)
			b[e[1]] = True
			for k in range(len(c[e[1]])):
				if b[k]:
					continue
				if d[e[1]] + c[e[1]][k] < d[k]:
					d[k] = d[e[1]] + c[e[1]][k]
					heapq.heappush(a, (d[k], k))
		ans += d[1]
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    
    H, W = [int(x) for x in input().split()]
    c = []
    for _ in range(10):
        c.append([int(x) for x in input().split()])
    A = []
    for _ in range(H):
        A.append([int(x) for x in input().split()])

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

    N = 10
    cost = warshall_floyd(c)
    ans = 0

    for i in A:
        for j in i:
            if j >= 0:
                ans += cost[j][1]

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
 
H, W = [int(x) for x in input().split()]
c = []
for _ in range(10):
    c.append([int(x) for x in input().split()])
A = []
for _ in range(H):
    A.append([int(x) for x in input().split()])

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

N = 10
cost = warshall_floyd(c)
ans = 0

for i in A:
    for j in i:
        if j >= 0:
            ans += cost[j][1]

print(ans)

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

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

cost = []
for i in range(10):
    tmp = 10 ** 10
    factor = [int(x) for x in range(10) if x != i]
    per = list(permutations(factor))
    for j in per:
        a = [i] + list(j)
        cnt = 0
        for k in range(9):
            if a[k + 1] != 1:
                cnt += c[a[k]][a[k + 1]]
            else:
                cnt += c[a[k]][a[k + 1]]
                tmp = min(tmp, cnt)
                break
    cost.append(tmp)
ans = 0
for i in A:
    for j in i:
        if j != 1 and j != -1:
            ans += cost[j]
print(ans)

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

H, W = map(int, input().split())
dpCost = [list(map(int, input().split())) for _ in range(10)]
area = [list(map(int, input().split())) for _ in range(H)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            dpCost[i][j] = min(dpCost[i][j], dpCost[i][k]+dpCost[k][j])
wall = Counter(chain.from_iterable(area))
ans = 0
for k, v in wall.items():
    if k == 1 or k == -1:
        continue
    ans += v * dpCost[k][1]
print(ans)

Solution (Python):
def main():
    h, w = map(int, 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)]

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

    ret = 0
    for row in a:
        for cell in row:
            if ~cell:
                ret += c[cell][1]

    print(ret)


if __name__ == '__main__':
    main()