gistfile1.txt

def parse_command():
    from sys import stdin as f
    n_tests = int(f.readline().strip())
    test_num = 0
    while test_num < n_tests:
        n_cities = int(f.readline().strip())
        cities = [int(x) for x in f.readline().strip().split()]
        W = []
        for _ in range(n_cities):
            line = [float("inf") if int(x) == -1 else int(x) for x in f.readline().strip().split()]
            W.append(line)
        test_num += 1
        yield W,cities


def extend(L,W):
    n = len(L)
    M = [[float("inf") for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            M[i][j] = min([L[i][k]+W[k][j] for k in range(n)])
    return M
def fast_all_pair(W):
    n = len(W)
    L = [[W[i][j] for j in range(n)] for i in range(n)]
    m = 1
    while m < n-1:
        L = extend(L,L)
        m *= 2
    return L

def main():
    g = parse_command()
    for W, C in g:
        L = fast_all_pair(W)
        path_cost = sum(L[C[i-1]][C[i]] for i in range(1,len(C))) + L[C[len(C)-1]][C[0]]
        if path_cost < float("inf"):
            print(str(path_cost))
        else: print("umulig")
main()