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 queue import Queue
import heapq
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(x): print(x, file=sys.stderr)



class Graph():
    """
    Graph のテンプレート。デフォルトは重みなしの有向グラフの隣接リスト形式での定義。
    Parameters
    --------
        n (int): グラフのサイズ。
    Options
    --------
        Weighted = False: 重み付きかどうか
        Directed = True: 有向かどうか
        Matrix = False:　グラフの表現を隣接リストにするか隣接行列にするか。デフォルトは隣接リスト。
    Methods
    -------
        add_edge(start,end,(weight))
            start から end に重さ weight の辺を張る。重みなしグラフの場合は weight を省略する。
        dijkstra(start): O((E+V)logV)
            start から各頂点への最短距離を返す。負の辺があると無理。
        bellman_ford(start): O(EV)
            start から各頂点への最短距離を返す。負の辺があってもいけるが遅い。
    """

    def __init__(self, n, Weighted=False, Directed=True, Matrix=False):
        self.sz = n
        self.is_Weighted = Weighted
        self.is_Directed = Directed
        self.is_Matrix = Matrix
        if Matrix:
            if Weighted:
                self.graph = [[float('inf') for _i in range(n)]
                              for _j in range(n)]
            else:
                self.graph = [[0 for _i in range(n)] for _j in range(n)]
        else:
            self.graph = [[] for _i in range(n)]

    def _weighted_add_edge(self, x, y, w):
        if self.is_Matrix:
            self.graph[x][y] = w
        else:
            self.graph[x].append((y, w))

    def _unweighted_add_edge(self, x, y):
        if self.is_Matrix:
            self.graph[x][y] = 1
        else:
            self.graph[x].append(y)

    def add_edge(self, x, y, *w):
        if self.is_Directed:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
            else:
                self._unweighted_add_edge(x, y)
        else:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
                self._weighted_add_edge(y, x, w[0])
            else:
                self._unweighted_add_edge(x, y)
                self._unweighted_add_edge(y, x)

    def _convert_to_maxrix(self):
        if self.is_Matrix:
            return self
        mat_g = self.__class__(
            self.sz,
            Weighted=self.is_Weighted,
            Directed=self.is_Directed,
            Matrix=True)
        if self.is_Weighted:
            for i in range(self.sz):
                for j in self.graph[i]:
                    mat_g.add_edge(i, j[0], j[1])
        else:
            for i in range(self.sz):
                for j in self.graph[i]:
                    mat_g.add_edge(i, j)
        return mat_g

    def __getitem__(self, n):
        return self.graph[n]

    
    
    

    def __str__(self):
        return str([self.graph[i] for i in range(self.sz)])

    def dijkstra(self, s):
        """
        単一始点最短距離を求める関数。dijkstra(s)でsからの任意の頂点への最短距離を求める。到達できなければfloat('inf')を返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならば bfs を使うか，グラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
        """
        if self.is_Matrix:
            print("隣接リスト形式で入力してください")
            raise TypeError
        d = [float('inf') for _ in range(self.sz)]
        b = [-1 for _ in range(self.sz)]  
        q = []
        d[s] = 0
        heapq.heappush(q, (d[s], s))
        while not len(q) == 0:
            p = heapq.heappop(q)
            v = p[-1]
            if d[v] < p[0]:
                continue
            if self.is_Weighted:
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[u] > d[v] + c:
                        d[u] = d[v] + c
                        b[u] = v
                        heapq.heappush(q, (d[u], u))
            else:
                for e in self.graph[v]:
                    u = e
                    if d[u] > d[v] + 1:
                        d[u] = d[v] + 1
                        b[u] = v
                        heapq.heappush(q, (d[u], u))
        return d

    def bellman_ford(self, s):
        """
        単一始点最短距離を求める関数。bellman_ford(s)でsからの任意の頂点への最短距離を求める。到達できなければ　float('inf')　を返す。負のサイクルがある場合は False のみを返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        d = [float('inf') for _ in range(self.sz)]
        d[s] = 0
        for i in range(self.sz - 1):
            for v in range(self.sz):
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[v] == float('inf'):
                        continue
                    d[u] = min(d[u], d[v] + c)
        for v in range(self.sz):
            for e in self.graph[v]:
                u = e[0]
                c = e[-1]
                if d[v] == float('inf'):
                    continue
                if d[u] > d[v] + c:
                    return False
        return d

    def warshall_froyd(self):
        """
        全頂点間最短距離を求める関数。warshall_froyd()で任意の頂点間の最短距離を求める。到達できなければ　float('inf')　を返す。
        負のサイクルがあるかどうかは自分自身との最短距離 d[i][i] の中に負のものがあるかどうかで分かる。

        Warning
        ----------
            隣接行列形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        d = self._convert_to_maxrix()
        for i in range(self.sz):
            d[i][i] = 0
        for k in range(self.sz):
            for i in range(self.sz):
                for j in range(self.sz):
                    if d[i][k] != float('inf') and d[k][j] != float('inf'):
                        d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d


def AOJ_ALDS_1_11_A():
    """
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A&lang=jp
    """
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    mat_g = g._convert_to_maxrix()
    for i in range(n):
        print(*mat_g[i])



def AOJ_ALDS_1_11_B():
    """
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=jp
    """
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    d = [-1] * n
    f = [-1] * n
    time = 0

    def dfs(G, v):
        nonlocal time
        time += 1
        d[v] = time
        for nv in G[v]:
            if d[nv] != -1:
                continue
            dfs(G, nv)
        time += 1
        f[v] = time

    for v in range(n):
        if d[v] != -1:
            continue
        dfs(g, v)
    for i in range(n):
        print(i + 1, d[i], f[i])



def AOJ_ALDS_1_11_C():
    """
    各頂点の0からの最短距離を bfs で求める
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
    """
    q = Queue()
    n = ii()
    dist = [-1 for _ in range(n)]
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    q.put(0)
    dist[0] = 0
    while not q.empty():
        v = q.get()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                q.put(nv)
    for i in range(n):
        print(i + 1, dist[i])



def AOJ_GRL_1_A():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp"""
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    for i in g.dijkstra(start):
        if i == float('inf'):
            print('INF')
        else:
            print(i)
    



def AOJ_ALDS_1_11_C_kai():
    """
    各頂点の0からの最短距離を dijkstra で求める。
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
    """
    n = ii()
    g = Graph(n, Weighted=True)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1, 1)
    dist = g.dijkstra(0)
    for i in range(n):
        if dist[i] == float('inf'):
            print(i + 1, -1)
        else:
            print(i + 1, dist[i])



def AOJ_GRL_1_B():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jp"""
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.bellman_ford(start)
    if d == False:
        print("NEGATIVE CYCLE")
    else:
        d = list(map(lambda x: x if x != float('inf') else 'INF', d))
        for i in d:
            print(i)



def AOJ_GRL_1_C():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=jp"""
    n, m = mi()
    g = Graph(n, Weighted=True, Directed=True, Matrix=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.warshall_froyd()
    d = [list(map(lambda x: x if x != float('inf') else 'INF', d[i]))
         for i in range(n)]
    for i in range(n):
        if d[i][i] < 0:
            print('NEGATIVE CYCLE')
            sys.exit()
    for i in d:
        print(*i)



def ABC132_E():
    """
    頂点3倍するdijkstra法。頂点倍加の典型例として
    https://atcoder.jp/contests/abc132/tasks/abc132_e
    """
    N, M = mi()
    g = Graph(3 * N)
    for i in range(M):
        a, b = mi()
        g.add_edge(a - 1, b + N - 1)
        g.add_edge(a + N - 1, b + 2 * N - 1)
        g.add_edge(a + 2 * N - 1, b - 1)
    S, T = mi()
    ans = g.dijkstra(S - 1)[T - 1]
    if ans == float('inf'):
        print(-1)
    else:
        print(ans // 3)


def ABC079_D():
    """https://atcoder.jp/contests/abc079/tasks/abc079_d"""
    H, W = mi()
    mat = [[] for __ in range(10)]
    for i in range(10):
        mat[i] = lmi()
    g = Graph(10, Matrix=True, Weighted=True)
    g.graph = mat
    cost = g.warshall_froyd()
    field = [[] for _ in range(H)]
    for i in range(H):
        field[i] = lmi()
    ans = 0
    for i in range(H):
        for j in range(W):
            if field[i][j] != -1:
                ans += cost[field[i][j]][1]
    print(ans)


if __name__ == '__main__':
    
    
    
    
    
    
    
    
    ABC079_D()

Solution (Python):
from queue import Queue
import heapq
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(x): print(x, file=sys.stderr)



class Graph():
    """
    Graph のテンプレート。デフォルトは重みなしの有向グラフの隣接リスト形式での定義。
    Parameters
    --------
        n (int): グラフのサイズ。
    Options
    --------
        Weighted = False: 重み付きかどうか
        Directed = True: 有向かどうか
        Matrix = False:　グラフの表現を隣接リストにするか隣接行列にするか。デフォルトは隣接リスト。
    Methods
    -------
        add_edge(start,end,(weight))
            start から end に重さ weight の辺を張る。重みなしグラフの場合は weight を省略する。
        dijkstra(start): O((E+V)logV)
            start から各頂点への最短距離を返す。負の辺があると無理。
        bellman_ford(start): O(EV)
            start から各頂点への最短距離を返す。負の辺があってもいけるが遅い。
    """

    def __init__(self, n, Weighted=False, Directed=True, Matrix=False):
        self.sz = n
        self.is_Weighted = Weighted
        self.is_Directed = Directed
        self.is_Matrix = Matrix
        if Matrix:
            if Weighted:
                self.graph = [[float('inf') for _i in range(n)]
                              for _j in range(n)]
            else:
                self.graph = [[0 for _i in range(n)] for _j in range(n)]
        else:
            self.graph = [[] for _i in range(n)]

    def _weighted_add_edge(self, x, y, w):
        if self.is_Matrix:
            self.graph[x][y] = w
        else:
            self.graph[x].append((y, w))

    def _unweighted_add_edge(self, x, y):
        if self.is_Matrix:
            self.graph[x][y] = 1
        else:
            self.graph[x].append((y, 1))

    def add_edge(self, x, y, *w):
        if self.is_Directed:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
            else:
                self._unweighted_add_edge(x, y)
        else:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
                self._weighted_add_edge(y, x, w[0])
            else:
                self._unweighted_add_edge(x, y)
                self._unweighted_add_edge(y, x)

    def _convert_to_maxrix(self):
        if self.is_Matrix:
            return self
        mat_g = self.__class__(
            self.sz,
            Weighted=self.is_Weighted,
            Directed=self.is_Directed,
            Matrix=True)
        for i in range(self.sz):
            for j in self.graph[i]:
                mat_g.add_edge(i, j[0], j[1])
        return mat_g

    def __getitem__(self, n):
        return self.graph[n]

    
    
    

    def __str__(self):
        return str([self.graph[i] for i in range(self.sz)])

    def dijkstra(self, s):
        """
        単一始点最短距離を求める関数。dijkstra(s)でsからの任意の頂点への最短距離を求める。到達できなければfloat('inf')を返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならば bfs を使うか，グラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
        """
        if self.is_Matrix:
            print("隣接リスト形式で入力してください")
            raise TypeError
        d = [float('inf') for _ in range(self.sz)]
        b = [-1 for _ in range(self.sz)]  
        q = []
        d[s] = 0
        heapq.heappush(q, (d[s], s))
        while not len(q) == 0:
            p = heapq.heappop(q)
            v = p[-1]
            if d[v] < p[0]:
                continue
            
            for e in self.graph[v]:
                u = e[0]
                c = e[-1]
                if d[u] > d[v] + c:
                    d[u] = d[v] + c
                    b[u] = v
                    heapq.heappush(q, (d[u], u))
            
            
            
            
            
            
            
        return d

    def bellman_ford(self, s):
        """
        単一始点最短距離を求める関数。bellman_ford(s)でsからの任意の頂点への最短距離を求める。到達できなければ　float('inf')　を返す。負のサイクルがある場合は False のみを返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        d = [float('inf') for _ in range(self.sz)]
        d[s] = 0
        for i in range(self.sz - 1):
            for v in range(self.sz):
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[v] == float('inf'):
                        continue
                    d[u] = min(d[u], d[v] + c)
        for v in range(self.sz):
            for e in self.graph[v]:
                u = e[0]
                c = e[-1]
                if d[v] == float('inf'):
                    continue
                if d[u] > d[v] + c:
                    return False
        return d

    def warshall_froyd(self):
        """
        全頂点間最短距離を求める関数。warshall_froyd()で任意の頂点間の最短距離を求める。到達できなければ　float('inf')　を返す。
        負のサイクルがあるかどうかは自分自身との最短距離 d[i][i] の中に負のものがあるかどうかで分かる。

        Warning
        ----------
            隣接行列形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        d = self._convert_to_maxrix()
        for i in range(self.sz):
            d[i][i] = 0
        for k in range(self.sz):
            for i in range(self.sz):
                for j in range(self.sz):
                    if d[i][k] != float('inf') and d[k][j] != float('inf'):
                        d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d


def AOJ_ALDS_1_11_A():
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    mat_g = g._convert_to_maxrix()
    for i in range(n):
        print(*mat_g[i])





def AOJ_ALDS_1_11_B():
    
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    d = [-1] * n
    f = [-1] * n
    time = 0

    def dfs(G, v):
        nonlocal time
        time += 1
        d[v] = time
        for nv in G[v]:
            if d[nv[0]] != -1:
                continue
            dfs(G, nv[0])
        time += 1
        f[v] = time

    for v in range(n):
        if d[v] != -1:
            continue
        dfs(g, v)
    for i in range(n):
        print(i + 1, d[i], f[i])




def AOJ_ALDS_1_11_C():
    """
    各頂点の0からの最短距離を bfs で求める
    """
    q = Queue()
    n = ii()
    dist = [-1 for _ in range(n)]
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    q.put(0)
    dist[0] = 0
    while not q.empty():
        v = q.get()
        for nv in g[v]:
            if dist[nv[0]] == -1:
                dist[nv[0]] = dist[v] + 1
                q.put(nv[0])
    for i in range(n):
        print(i + 1, dist[i])




def AOJ_GRL_1_A():
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    for i in g.dijkstra(start):
        if i == float('inf'):
            print('INF')
        else:
            print(i)
    




def AOJ_ALDS_1_11_C_kai():
    """
    各頂点の0からの最短距離を dijkstra で求める
    """
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    dist = g.dijkstra(0)
    for i in range(n):
        if dist[i] == float('inf'):
            print(i + 1, -1)
        else:
            print(i + 1, dist[i])




def AOJ_GRL_1_B():
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.bellman_ford(start)
    if d == False:
        print("NEGATIVE CYCLE")
    else:
        d = list(map(lambda x: x if x != float('inf') else 'INF', d))
        for i in d:
            print(i)




def AOJ_GRL_1_C():
    n, m = mi()
    g = Graph(n, Weighted=True, Directed=True, Matrix=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.warshall_froyd()
    d = [list(map(lambda x: x if x != float('inf') else 'INF', d[i]))
         for i in range(n)]
    for i in range(n):
        if d[i][i] < 0:
            print('NEGATIVE CYCLE')
            sys.exit()
    for i in d:
        print(*i)




def ABC132_E():
    """
    頂点3倍するdijkstra法。頂点倍加の典型例として
    """
    N, M = mi()
    g = Graph(3 * N)
    for i in range(M):
        a, b = mi()
        g.add_edge(a - 1, b + N - 1)
        g.add_edge(a + N - 1, b + 2 * N - 1)
        g.add_edge(a + 2 * N - 1, b - 1)
    S, T = mi()
    ans = g.dijkstra(S - 1)[T - 1]
    if ans == float('inf'):
        print(-1)
    else:
        print(ans // 3)


def ABC079_D():
    H, W = mi()
    mat = [[] for __ in range(10)]
    for i in range(10):
        mat[i] = lmi()
    g = Graph(10, Matrix=True, Weighted=True)
    g.graph = mat
    cost = g.warshall_froyd()
    field = [[] for _ in range(H)]
    for i in range(H):
        field[i] = lmi()
    ans = 0
    for i in range(H):
        for j in range(W):
            if field[i][j] != -1:
                ans += cost[field[i][j]][1]
    print(ans)


if __name__ == '__main__':
    
    
    
    
    
    
    
    
    ABC079_D()

Solution (Python):
inf = 1000000000
H,W = map(int,input().split())
C = [[int(j) for j in input().split()] for i in range(10)]


for m in range(10):
    for s in range(10):
        for g in range(10):
                C[s][g] = min(C[s][g],C[s][m] + C[m][g])

def maryoku(x):
    if x == -1:return(0)
    else:return(C[x][1])

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

print(sum([sum([maryoku(aa) for aa in a]) for a in A]))

Solution (Python):
def minindex(arrived,costs):
    mindex = "end"
    curmin = 100000000
    for i in range(10):
        if arrived[i]:continue
        if curmin>costs[i]:
            mindex = i
            curmin = costs[i]
    return mindex

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



arrived = [False] * 10
arrived[1] = True
costs = [1000000] * 10
costs[1] = 0
curpos = 1
for i in range(10):
    for j,done in enumerate(arrived):
        costs[j] = min(costs[j],costs[curpos] + C[j][curpos])
    if i==9:break
    curpos = minindex(arrived,costs)
    arrived[curpos] = True
A = [[int(i) for i in input().split()] for j in range(H)]

def maryoku(x):
    if x == -1:return(0)
    else:return(costs[x])

print(sum([sum([maryoku(aa) for aa in a]) for a in A]))

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

for k in range(10):
    for i in range(10):
        if graph[i][k] == 0:
            continue
        for j in range(10):
            if graph[k][j] == 0:
                continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
            
print(sum(graph[v][1] for c in A for v in c if v != -1))

Solution (Python):
if __name__ == '__main__':
    [H, W] = [int(i) for i in input().split()]
    dist = [[0] * 10 for _ in range(10)]

    for i in range(10):
        for j, c in enumerate([int(i) for i in input().split()]):
            dist[i][j] = c

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

    result = 0

    for h in range(H):
        for w, a in enumerate([int(i) for i in input().split()]):
            if a != -1:
                result += dist[a][1]


    print(result)

Solution (Python):
H, W = map(int, input().split())
dist = [[0]*10 for _ in range(10)]
for i in range(10):
    for j, c in enumerate(input().split()):
        dist[i][j] = int(c)
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])
count = 0
for _ in range(H):
    for a in input().split():
        if not int(a) == -1:
            count += dist[int(a)][1]
print(count)

Solution (Python):

import string
import sys
from itertools import chain, dropwhile, takewhile


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[fill_value]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    H, W = readi(2)
    G = readi(10, 10)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

    ans = 0
    for a in chain.from_iterable(readi(H, W)):
        if a != -1:
            ans += G[a][1]

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
graph=[]
h,w=map(int,input().split())
for i in range(10):
    graph.append(list(map(int,input().split())))
graph = csr_matrix(graph)

d, p = floyd_warshall(csgraph=graph, directed=True, return_predecessors=True)

dic={-1:0}
for i in range(10):
    dic[i]=d[i][1]
ans=0
for i in range(h):
    for j in map(int,input().split()):
        ans+=dic[j]
print(int(ans))

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


if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int, input().split())

c = []
for i in range(10):
	row = list(input().split())
	for j in range(10):
		row[j] = int(row[j])
	c.append(row)
	
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(n):
	row = list(input().split())
	for j in range(m):
		row[j] = int(row[j])
		if row[j] == 1 or row[j] == -1:
			continue
		ans += c[row[j]][1]
			
print(ans)

Solution (Python):
H,W=map(int,input().split())
d=[]
for i in range(10):
  l=list(map(int,input().split()))
  d.append(l)
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):
  l=list(map(int,input().split()))
  for j in l:
    if j==-1:
      continue
    ans+=d[j][1]
print(ans)

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

def floyd_warshall(V, E):
    INF = float('inf')
    N = len(V)
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for u, c in E[v].items(): dist[v][u] = c
    for k, i, j in product(V, repeat=3):
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist
        
H, W = map(int, input().split())
E = {i: defaultdict(int) for i in range(10)}
for i in range(10):
    C = map(int, input().split())
    for j, c in enumerate(C):
        E[i][j] = c
A = []
for _ in range(H):
    A += list(map(int, input().split()))
n_num = {i: A.count(i) for i in range(10)}
V = list(range(10))
cost = floyd_warshall(V, E)
print(sum([cost[i][1]*n_num[i] for i in range(10)]))

Solution (Python):

import sys
import copy

def pl2(L):
    for l in L:
        print(l)

def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    c2 = []
    while True:
        is_updated = False 
        c2 =  copy.deepcopy(c)
        for i in range(10):
            for j in range(10):
                if i != j:
                    for k in range(10):
                        if c2[i][j] > c[i][k]+c[k][j]:
                            c2[i][j] = c[i][k]+c[k][j]
                            is_updated = True
        if not is_updated:
            break
        else:
            c = copy.deepcopy(c2)

    res = 0
    for a in A:
        for c in a:
            if abs(c) != 1:
                res += c2[c][1]

    print(res)








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):
from scipy.sparse.csgraph import dijkstra
H,W = map(int,input().split())
g = [list(map(int,input().split())) for _ in range(10)]
d = dijkstra(g)
ans = 0
for _ in range(H):
    A = list(map(int,input().split()))
    for i in range(W):
        if A[i] != -1:
            ans += d[A[i]][1]
print(int(ans))

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

Solution (Python):
from scipy.sparse import*
a=[[abs(int(t))for t in t.split()]for t in open(0)]
print(int(sum(csgraph.dijkstra(csr_matrix(a[1:11]))[sum(a[11:],[]),1])))