There are N towns in the State of Atcoder, connected by M bidirectional roads.
The i-th road connects Town A_i and B_i and has a length of C_i.
Joisino is visiting R towns in the state, r_1,r_2,..,r_R (not necessarily in this order).
She will fly to the first town she visits, and fly back from the last town she visits, but for the rest of the trip she will have to travel by road.
If she visits the towns in the order that minimizes the distance traveled by road, what will that distance be?

-----Constraints-----
 - 2≤N≤200
 - 1≤M≤N×(N-1)/2
 - 2≤R≤min(8,N) (min(8,N) is the smaller of 8 and N.)
 - r_i≠r_j (i≠j)
 - 1≤A_i,B_i≤N, A_i≠B_i
 - (A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)
 - 1≤C_i≤100000
 - Every town can be reached from every town by road.
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M R
r_1 ... r_R
A_1 B_1 C_1
:
A_M B_M C_M

-----Output-----
Print the distance traveled by road if Joisino visits the towns in the order that minimizes it.

-----Sample Input-----
3 3 3
1 2 3
1 2 1
2 3 1
3 1 4

-----Sample Output-----
2

For example, if she visits the towns in the order of 1, 2, 3, the distance traveled will be 2, which is the minimum possible.

Difficulty: interview

Starter code:

Solutions:
from itertools import permutations as p

from scipy.sparse.csgraph import floyd_warshall

n, m, r = map(int, input().split())
R = list(map(int, input().split()))
l = [[0]*n for _ in range(n)]
for _ in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  l[a][b] = c
  l[b][a] = c
F = floyd_warshall(l)

ans = float("inf")
for v in p(R):
  temp = 0
  for i in range(r-1):
    temp += F[v[i]-1][v[i+1]-1]
  ans = min(ans, temp)
  
print(int(ans))

import itertools
import sys
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall
input = sys.stdin.readline


n, m, r = list(map(int, input().split()))
visiting_town = list(map(int, input().split()))
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = list(map(int, input().split()))
    edges[a-1][b-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
comp_dist = floyd_warshall(G, directed=False)

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        dist = comp_dist[_from-1][to-1]
        result += dist
    candidates.append(result)

print((int(min(candidates))))


def main():
    import itertools
    n,m,r=list(map(int,input().split()))
    rx=[int(i) for i in input().split()]
    inf=100000000
    wf=[[inf]*n for i in range(n)]
    for i in range(n):
        wf[i][i]=0

    for i in range(m):
        a,b,c=list(map(int,input().split()))
        wf[a-1][b-1]=c
        wf[b-1][a-1]=c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if wf[i][j]>wf[i][k]+wf[k][j]:
                    wf[i][j]=wf[i][k]+wf[k][j]
    cnt=0
    l=list(itertools.permutations([i for i in range(r)]))
    cnt=inf
    for i in l:
        cnt_sub=0
        for j in range(r-1):
            cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
        cnt=min(cnt,cnt_sub)
    print(cnt)
main()


import itertools as it
n,m,r=map(int,input().split())
ll=list(map(int,input().split()))
d=[[float("inf") for _ in range(n)] for _ in range(n)] #各頂点から各頂点への最小コスト
for i in range(m): #重複なしver
    a,b,t=map(int,input().split())
    d[a-1][b-1]=t
    d[b-1][a-1]=t #有向グラフの場合消す
for i in range(n):
    d[i][i]=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]
ans=10**9
for p in it.permutations(ll):
    tmp=0
    for j in range(r-1):
        s,g=p[j]-1,p[j+1]-1
        tmp+=d[s][g]
    ans=min(ans,tmp)
print(ans)

import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, R = MAP()
r = LIST()
ABC = [LIST() for _ in range(M)]

dist_matrix = [[0]*N for _ in range(N)]
for A, B, C in ABC:
	dist_matrix[A-1][B-1] = C
	dist_matrix[B-1][A-1] = C

#for i in range(N):
#	print(dist_matrix[i])

#ワーシャルフロイド法  注意 PyPy非対応!!!!
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
 
graph = csr_matrix(dist_matrix) #隣接行列からcsr行列をつくる
dist_matrix = floyd_warshall(graph, directed=False) #無向の場合directed=False
#dist_matrixの中身はfloatになっているので注意！

#for i in range(N):
#	print(dist_matrix[i])

ans = INF
for x in permutations(r):
	dis = 0
	for i in range(1, R):
		dis += dist_matrix[x[i-1]-1][x[i]-1]
	ans = min(ans, dis)

print((int(ans)))


	


# ABC073 D - joisino's travel
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))

inf = 10**18
dist = [[inf]*N for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    dist[A-1][B-1] = dist[B-1][A-1] = C

dist = floyd_warshall(dist)

ans = inf
for rr in permutations(r):
    cost = 0
    for i in range(R-1):
        cost += dist[rr[i]-1][rr[i+1]-1]
    if cost < ans:
        ans = cost
print(int(ans))

import itertools
from scipy.sparse.csgraph import floyd_warshall

N, M, R = list(map(int, input().split()))
r = tuple(map(int, input().split()))

INF = 10**10

d = [[INF] * N for _ in range(N)]

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

for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c

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

d = floyd_warshall(d)


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]-1][p[i+1]-1]

    ans = min(ans, dist)

print((int(ans)))


from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from itertools import permutations

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))

d = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    A, B, C = list(map(int, input().split()))
    d[A][B] = C
    d[B][A] = C
g = csgraph_from_dense(d)
g = floyd_warshall(g)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += g[p[i]][p[i + 1]]
    result = min(result, t)
print((int(result)))


import sys
from collections import defaultdict
from heapq import heapify,heappush,heappop
readline=sys.stdin.readline

def main():
    N,M,R=list(map(int,readline().split()))
    r=list(map(int,readline().split()))
    ew=[tuple(map(int,readline().split())) for _ in range(M)]
    edges=defaultdict(list)
    wt=defaultdict(int)
    for e in ew:
        edges[e[0]].append(e[1])
        edges[e[1]].append(e[0])
        wt[(e[0],e[1])]=e[2]
        wt[(e[1],e[0])]=e[2]
    inf=float('inf')
    def dijkstra(v):
        dist=[inf]*(N+1)
        dist[v]=0
        vw=[(0,v)]
        heapify(vw)
        while vw:
            cvw=heappop(vw)
            if cvw[0]>dist[cvw[1]]:
                continue
            for w in edges[cvw[1]]:
                cand=cvw[0]+wt[(cvw[1],w)]
                if dist[w]>cand:
                    dist[w]=cand
                    heappush(vw,(cand,w))
        return dist
    distdict=dict((v,dijkstra(v)) for v in r)
    mindist=inf
    def permlist(lst):
        tmp=[]
        if not lst:
            return [[]]
        for i,x in enumerate(lst):
            lstx=lst[:i]+lst[i+1:]
            ret=permlist(lstx)
            for e in ret:
                e.append(x)
            tmp.extend(ret)
        return tmp
    #print(distdict,permlist(r))
    pathlist=[sum([distdict[v][w] for v,w in zip(lst,lst[1:])]) for lst in permlist(r)]
    print((min(pathlist)))

def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def warshallFloyd():
    for k in range(N):
        for i in range(N-1):
            for j in range(i, N):
                tmp = min(E[i][j], E[i][k] + E[k][j])
                E[i][j] = E[j][i] = tmp

def dfs(c, p, d):
    if c == R:
        ans[0] = min(ans[0], d)
        return
    for i in range(R):
        if used[i]:
            continue
        used[i] = True
        if p == -1:
            dfs(c+1, i, 0)
        else:
            dfs(c+1, i, d + E[S[p]-1][S[i]-1])
        used[i] = False

N, M, R = map(int, input().split())
S = list(map(int, input().split()))
E = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    E[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a][b] = E[b][a] = c
warshallFloyd()
ans = [float('inf')]
used = [False] * R
dfs(0, -1, 0)
print(*ans)

import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

input = sys.stdin.readline
ans = -1

n, m, r = list(map(int, input().split()))
r  = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(m):
    a, b, c = list(map(int, input().split()))
    A.append(a-1)
    B.append(b-1)
    C.append(c)

wf = floyd_warshall(csr_matrix((C, (A, B)), shape = (n, n)), directed=False)

for pi in permutations(r):
    cand = 0
    for r1, r2 in zip(pi, pi[1:]):
        cand += int(wf[r1-1][r2-1])
    if ans < 0 or ans > cand:
        ans = cand

print(ans)


#!/usr/bin/env python3
import sys

def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    import numpy as np    
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import permutations, islice
    from functools import reduce
    # coo_matrix((data, (i, j)), [shape=(M, N)])
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1), dtype=np.int32).tocsr(), directed=False)
    f = lambda a, b: (a[0]+mat[a[1]][b], b)
    return int(min(reduce(f, q, (0, s))[0] for s, *q in permutations(r)))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    r = [int(next(tokens)) for _ in range(R)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    print((solve(N, M, R, r, A, B, C)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
n,m,r=map(int,input().split())
vis=list(map(int,input().split()))
INF=10**18
path=[[INF]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  path[a-1][b-1]=c
  path[b-1][a-1]=c
path=floyd_warshall(path)
ans=10**18
for root in permutations(vis):
  cnt=0
  for j in range(1,r):
    cnt+=path[root[j-1]-1][root[j]-1]
  ans=min(ans,cnt)
print(int(ans))

import sys
from itertools import permutations


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


def main():
    N, M, R = list(map(int, input().split()))

    def warshall_floyd(d):
        # d[i][j]: iからjへの最短距離
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    tmp = d[i][k] + d[k][j]
                    if d[i][j] > tmp:
                        d[i][j] = tmp
        return d

    r = list(map(int, input().split()))
    d = [[float("inf")] * N for i in range(N)]
    for i in range(M):
        x, y, z = list(map(int, input().split()))
        d[x - 1][y - 1] = z
        d[y - 1][x - 1] = z
    for i in range(N):
        d[i][i] = 0  # 自身のところに行くコストは０
    D = warshall_floyd(d)
    P = list(permutations(r))
    cost = float("inf")
    for p in P:
        c = 0
        for i in range(R - 1):
            c += D[p[i] - 1][p[i + 1] - 1]
        if c < cost:
            cost = c
    print(cost)


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import floyd_warshall
    matrix = [[0]*N for _ in range(N)]
    for i in range(M):
        matrix[A[i]-1][B[i]-1] = C[i]
        matrix[B[i]-1][A[i]-1] = C[i]
    
    dist_matrix = floyd_warshall(csgraph=matrix, directed=False)

    perm = list(itertools.permutations(r)) 

    answer = float('inf')
    for p in perm:
        a = 0
        for index in range(len(p)-1):
            a += dist_matrix[p[index]-1][p[index+1]-1]
        answer = min(answer,a)
    print((int(answer)))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    r = [int(next(tokens)) for _ in range(R)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, R, r, A, B, C)

def __starting_point():
    main()

__starting_point()

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations
n,m,r,*L=map(int,open(0).read().split())
f=floyd_warshall(csr_matrix((L[r+2::3],(L[r::3],L[r+1::3])),(n+1,n+1)),0)
print(int(min(sum(f[s,t]for s,t in zip(o,o[1:]))for o in permutations(L[:r]))))

import itertools
import numpy as np
from scipy.sparse.csgraph import shortest_path

N,M,R = map(int, input().split())
rs = np.array(list(map(int, input().split()))) -1

nodes = np.full((N,N), np.inf) 
for i in range(M):
  a,b,c = map(int, input().split())
  nodes[a-1,b-1] = nodes[b-1,a-1] = c
min_ds = shortest_path(nodes)
res = float('inf')
for p in itertools.permutations(rs):
  prev = p[0]
  tmp = 0
  for next in p[1:]:
    tmp += min_ds[prev,next]
    prev = next
  res = min(res, tmp)

print(int(res))

def main():
  import numpy as np
  import itertools
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  import sys
  readline = sys.stdin.readline
  readlines = sys.stdin.readlines

  N, M, R= map(int, readline().split())
  r = list(map(int,input().split()))
  lines = readlines()
  edge = np.array([line.split() for line in lines], dtype = np.int64).T
  graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
  distance_mat = floyd_warshall(graph,directed = False)
  #print(distance_mat)
  ans = float("inf")
  for town in itertools.permutations(r,R):
    #print(town)
    tmp = 0
    for i in range(R-1):
      tmp += distance_mat[town[i]-1][town[i+1]-1]
    ans = min(ans,tmp)
  print(int(ans))
main()

import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
from itertools import permutations

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m, R = I[:3]
r = I[3:3+R] - 1
a, b, c = I[3+R:].reshape(-1, 3).T
a -= 1; b -= 1
graph = csr_matrix((c, (a, b)), shape=(n, n))

def main():
    dist = floyd_warshall(graph, directed=False).astype(np.int64)
    *perms, = permutations(r)
    perms = np.array(perms)
    res = dist[perms[:, :-1], perms[:, 1:]]
    ans = np.amin(np.sum(res, axis=1))
    return ans

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

import itertools
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
N, M, R = list(map(int, input().split()))
r = [int(i) for i in input().split()]

G = [[10**8]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A, B, C = list(map(int, input().split()))
    G[A][B] = C
    G[B][A] = C

DG = csgraph_from_dense(G, null_value=10**8)
d = floyd_warshall(DG)

ans = 10**8
for route in itertools.permutations(r):
    c = 0
    for i in range(len(route)-1):
        c += d[route[i]][route[i+1]]
    ans = min(ans, c)
print((int(ans)))


import heapq
from itertools import permutations
n, m, r = list(map(int, input().split()))
R = list([int(x)-1 for x in input().split()])
edges = [[]for _ in range(n)]
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    edges[a].append((c, b))
    edges[b].append((c, a))


def dijkstra(init_v):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


dists = []
for x in R:
    dist = dijkstra(x)
    dists.append(dist)

INF = 10**18
ans = INF
for subset in permutations(list(range(r))):
    d = 0
    for v, v2 in zip(subset, subset[1:]):
        d += dists[v][R[v2]]
    if d < ans:
        ans = d

print(ans)


# ABC073 D - joisino's travel
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))

inf = 10**18
dist = [[inf]*N for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    dist[A-1][B-1] = dist[B-1][A-1] = C

dist = floyd_warshall(dist)

ans = inf
for rr in permutations(r):
    cost = 0
    for i in range(R-1):
        cost += dist[rr[i]-1][rr[i+1]-1]
    ans = min(ans, cost)
print(int(ans))

from itertools import permutations

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph._shortest_path import floyd_warshall


def solve():
    N, M, R = list(map(int, input().split()))
    r = list([int(x)-1 for x in input().split()])
    dist = [[0 for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        A, B, C = list(map(int, input().split()))
        dist[A-1][B-1] = C
        dist[B-1][A-1] = C
    fw = floyd_warshall(csr_matrix(dist))
    
    ans = 10**12
    for visit in permutations(r, R):
        m_sum = 0
        for i in range(R-1):
            m_sum += fw[visit[i]][visit[i+1]]
        ans = min(ans, m_sum)
    print((int(ans)))


def __starting_point():
    solve()

__starting_point()

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

n, m, r = map(int,input().split()) #n:頂点数　m:辺の数 r:訪れる町の数
R = list(map(int,input().split()))

d = np.array([[float("inf") for i in range(n)] for i in range(n)])
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    x, y, z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
wa = floyd_warshall(d)

# 訪れる町の順番を順列で用意
from itertools import permutations
ptn = permutations(R)

ans = 10**19
for p in ptn:
  cost = 0
  roots = [(j-1, i-1) for i, j in zip(p, p[1:])]
  for i, j in roots:
    cost += wa[i][j]
  ans = min(ans, cost)
  
print(int(ans))

import itertools


def dijkstra(v, G):
    import heapq

    ret = [10 ** 10] * len(G)
    ret[v] = 0
    q = [(ret[i], i) for i in range(len(G))]
    heapq.heapify(q)

    while len(q):
        tmpr, u = heapq.heappop(q)
        if tmpr == ret[u]:
            for w, l in G[u]:
                if ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l
                    heapq.heappush(q, (ret[w], w))
    return ret


N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
NE = [[] for _ in range(N)]
for _ in range(M):
    A, B, C = list(map(int, input().split()))
    NE[A - 1].append((B - 1, C))
    NE[B - 1].append((A - 1, C))

RE = [[0] * R for _ in range(R)]
for iR in range(R):
    for jR in range(iR + 1, R):
        lR = dijkstra(r[iR] - 1, NE)[r[jR] - 1]
        RE[iR][jR] = lR
        RE[jR][iR] = lR

ans = 10 ** 10
for p in itertools.permutations(list(range(R))):
    ans = min(ans, sum([RE[p[i]][p[i + 1]] for i in range(R - 1)]))

print(ans)


# solution

import itertools
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

int1 = lambda x: int(x) - 1

N, M, R = map(int, input().split())
T = sorted(list(map(int1, input().split())))
A = np.array([tuple(map(int, input().split())) for _ in range(M)]).T

matr = csr_matrix((A[2], (A[0] - 1, A[1] - 1)), shape=(N, N))
way = [dijkstra(matr, indices=t, directed=False)[T].astype(int).tolist() for t in T]

result = float('inf')
for t in itertools.permutations(range(R)):
    tmp = 0
    for i in range(R - 1):
        tmp += way[t[i]][t[i + 1]]
    result = min(result, tmp)
print(result)

# -*- coding: utf-8 -*-

import sys

from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, R = MAP()
A = [a-1 for a in LIST()]
G = list2d(N, N, INF)
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    G[a][b] = c
    G[b][a] = c

# 全体グラフの最短距離(ここから必要な頂点間だけ使う)
wf = floyd_warshall(G)

ans = INF
for r in range(R):
    # TSP(巡回セールスマン)
    dp = list2d(1<<R, R, INF)
    dp[1<<r][r] = 0
    for bit in range(1, (1<<R)-1):
        for i in range(R):
            if not (bit >> i & 1):
                continue
            for j in range(R):
                if bit >> j & 1:
                    continue
                a, b = A[i], A[j]
                dp[bit|1<<j][j] = min(dp[bit|1<<j][j], dp[bit][i] + int(wf[a,b]))
    ans = min(ans, min(dp[-1]))
print(ans)


import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import itertools
I = [int(_) for _ in open(0).read().split()]
N, M, R = I[:3]
r = np.array(I[3:3 + R])
ABC = I[3 + R:]
F = floyd_warshall(csr_matrix((ABC[2::3], (ABC[::3], ABC[1::3])), (N + 1, N + 1)), 0).astype(np.int64)
ans = float('inf')
for root in itertools.permutations(r, R):
    ans = min(ans, sum(F[i,j] for i, j in zip(root, root[1:])))
print(ans)


#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations


def main():
    N, M, R = map(int,input().split()) #N:頂点数　M:辺の数
    d = [[float("inf")]*N for i in range(N)]
    #d[u][v] : 辺uvのコスト(存在しないときはinf)
    r = list(map(int,input().split()))
    for i in range(M):
        u, v, w = map(int,input().split())
        d[u-1][v-1] = w
        d[v-1][u-1] = w
    for i in range(N):
        d[i][i] = 0 #自身のところに行くコストは０
    cost = floyd_warshall(d)
    L = list(permutations(r, R))
    ret = 10**9
    for rt in L:
        cos = 0
        for i in range(1,R):
            cos += cost[rt[i]-1][rt[i-1]-1]
        ret = min(ret, cos)
    print(int(ret))

def __starting_point():
    main()
__starting_point()

from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
INF = 1001001001

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
graph = [[INF]*N for _ in range(N)]
for i in range(M):
    A, B, C = list(map(int, input().split()))
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C
dist_matrix = floyd_warshall(graph)

ans = INF
for root in permutations(r):
    cnt = 0
    for j in range(R-1):
        cnt += dist_matrix[root[j]-1][root[j+1]-1]
    ans = min(ans, cnt)
print((int(ans)))


from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
from itertools import permutations

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(M)]

r = [e - 1 for e in r]

g = [[0] * N for _ in range(N)]
for a, b, c in abc:
	a -= 1
	b -= 1
	g[a][b] = c
	g[b][a] = c

dist = floyd_warshall(csr_matrix(g))

ans = float("inf")
for pat in permutations(r, len(r)):
	sm = 0
	for e1, e2 in zip(pat, pat[1:]):
		sm += dist[e1][e2]

	ans = min(ans, sm)

ans = int(ans)
print(ans)


from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

N, M, R = map(int, input().split())

s = [[10**9]*N for i in range(N)]
t = list(map(int, input().split()))
for i in range(M):
    a, b, c = map(int, input().split())
    s[a-1][b-1] = c
    s[b-1][a-1] = c
    
s = floyd_warshall(s)
ans = float('inf')
for i in permutations(t):
    A_n = 0
    for j in range(R-1):
        A_n += s[i[j] - 1][i[j+1] - 1]
    ans = min(ans, A_n)
    
print(int(ans))

import sys
from itertools import permutations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, R = list(map(int, readline().split()))
    city = [int(s) - 1 for s in readline().split()]
    ABC = list(map(int, read().split()))

    G = [[INF] * N for _ in range(N)]
    for a, b, c in zip(*[iter(ABC)] * 3):
        G[a - 1][b - 1] = G[b - 1][a - 1] = c

    for i in range(N):
        G[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]

    ans = INF
    for plan in permutations(city):
        res = 0
        for i in range(R - 1):
            res += G[plan[i]][plan[i + 1]]
        if ans > res:
            ans = res

    print(ans)
    return


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
import sys

def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import permutations
    from functools import reduce
    # coo_matrix((data, (i, j)), [shape=(M, N)])
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1)).tocsr(), directed=False)
    f = lambda a, b: (a[0]+mat[a[1]][b], b)
    return int(min(reduce(f, q, (0, s))[0] for s, *q in permutations(r)))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    r = [int(next(tokens)) for _ in range(R)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    print(solve(N, M, R, r, A, B, C))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()
__starting_point()

n,m,r_=list(map(int,input().split()))
r=list(map(int,input().split()))
g=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=list(map(int,input().split()))
  a-=1
  b-=1
  g[a].append([b,c])
  g[b].append([a,c])
from heapq import heapify,heappush,heappop
def dks(t0,t1):
  kyori=[-1]*n
  todo=[[0,t0]]
  heapify(todo)
  while todo:
    d,t=heappop(todo)
    kyori[t]=d
    if t==t1:break
    l=g[t]
    for li,c in l:
      if kyori[li]==-1:
        heappush(todo,[c+d,li])
  return kyori[t1]
ans=pow(10,9)
allr=[]
import sys
sys.setrecursionlimit(10**7)
def dfs(s,k): #s:list, k:set
  if len(k)==1:
    s.append(k.pop())
    return [s]
  ret=[]
  for ki in k:
    ret.extend(dfs(s+[ki],k-{ki}))
  return ret
allr=dfs([],set(r))
d={}
for i in range(r_-1):
  for j in range(i+1,r_):
    k=dks(r[i]-1,r[j]-1)
    d[r[i]-1,r[j]-1]=k
    d[r[j]-1,r[i]-1]=k

for j in range(len(allr)):
  r1=allr[j]
  ansi=0
  for i in range(r_-1):
    ansi+=d[(r1[i]-1,r1[i+1]-1)]
  ans=min(ans,ansi)
print(ans)


#!/usr/bin/env python3

from itertools import permutations
import numpy as np

HUGE = 10 ** 18

def main():
    n, m, r = list(map(int, input().split()))
    togo = list(map(int, input().split()))
    adj_mat = [[HUGE for j in range(n)] for i in range(n)]
    for i in range(n):
        adj_mat[i][i] = HUGE
    for i in range(m):
        a, b, c = list(map(int, input().split()))
        a0 = a - 1
        b0 = b - 1
        adj_mat[a0][b0] = c
        adj_mat[b0][a0] = c
    adj_mat = np.array(adj_mat)

    wf(adj_mat, n)

    res = HUGE
    for way in permutations(togo):
        assert len(way) > 1
        x = 0
        for i in range(len(way) - 1):
            x += adj_mat[way[i] - 1][way[i + 1] - 1]
        res = min(res, x)

    print(res)

def wf(adj_mat, n):
    for k in range(n):
        for i in range(n):
            adj_mat[i, :] = np.minimum(adj_mat[i, :], adj_mat[i][k] + adj_mat[k, :])

def __starting_point():
    main()

__starting_point()

import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, R = MAP()
r = LIST()
ABC = [LIST() for _ in range(M)]

dist_matrix = [[INF]*N for _ in range(N)]

for A, B, C in ABC:
	dist_matrix[A-1][B-1] = C
	dist_matrix[B-1][A-1] = C

for i in range(N):
	dist_matrix[i][i] = 0

#for i in range(N):
#	print(dist_matrix[i])

#ワーシャルフロイド法  注意 PyPy非対応!!!!
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
 
graph = csr_matrix(dist_matrix) #隣接行列からcsr行列をつくる
dist_matrix = floyd_warshall(graph, directed=False) #無向の場合directed=False
#dist_matrixの中身はfloatになっているので注意！

#for i in range(N):
#	print(dist_matrix[i])

ans = INF
for x in permutations(r):
	tmp = 0
	for i in range(1, R):
		tmp += dist_matrix[x[i-1]-1][x[i]-1]
	ans = min(ans, tmp)

print((int(ans)))
	


from itertools import permutations
import sys
input = sys.stdin.readline

def main():
    N, M, RR = map(int, input().split())
    R = list(map(int, input().split()))
    INF = float("inf")
    T = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = tuple(map(int, input().split()))
        T[a-1][b-1] = c
        T[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if T[i][j] > T[i][k]+T[k][j]:
                    T[i][j] = T[i][k]+T[k][j]
    ans = INF
    for rs in permutations(R):
        cost = 0
        for i in range(RR-1):
            cost += T[rs[i]-1][rs[i+1]-1]
        ans = min(ans, cost)
    print(ans)

def __starting_point():
    main()
__starting_point()

from itertools import permutations as p
 
from scipy.sparse.csgraph import floyd_warshall
 
n, m, r = map(int, input().split())
R = list(map(int, input().split()))
l = [[0]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    l[a][b] = c
    l[b][a] = c
F = floyd_warshall(l)
 
ans = float("inf")
for v in p(R):
    temp = 0
    for i in range(r-1):
        temp += F[v[i]-1][v[i+1]-1]
    ans = min(ans, temp)
print(int(ans))

n,m,R = map(int,input().split())
r = list(map(int,input().split()))

from itertools import permutations
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
cost = np.ones((n,n))*float('inf')
for i in range(m):
    a,b,c = map(int,input().split())
    cost[a-1][b-1]=cost[b-1][a-1]=c
d = floyd_warshall(cost)
def main():
    m = float('inf')

    for j in permutations(r):
        l = 0
        for i in range(len(j)-1):
            s,t = j[i],j[i+1]
            l += d[s-1][t-1]
        if l<m:
            m = l
    print(int(m))


def __starting_point():
    main()
__starting_point()

# https://atcoder.jp/contests/abc073/tasks/abc073_d

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))



# default import
from itertools import product, permutations, combinations

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

# ダイクストラか？
# 全点間の最小距離を取得
# rについてpermutationして。その通りに訪れたときの距離をシミュレーション
# 最小値を選ぶ

N, M, r = read_ints()
R = [x - 1 for x in read_ints()]
adj_mat = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj_mat[a][b] = c
    adj_mat[b][a] = c

# print(csr_matrix(adj_mat, dtype='int'))
D = dijkstra(csr_matrix(adj_mat, dtype='int'), directed=False)
# print(D)
# 全探索パート
ans = 2 ** 31


def get_kyori(p):
    ret = 0
    for ps, pt in zip(p[:-1], p[1:]):
        ret += D[ps, pt]
    return ret


for p in permutations(R):
    ans = min(ans, get_kyori(p))
print((int(ans)))


import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M, R = list(map(int, input().split()))

RS = list(map(int, input().split()))

G = [[] for _ in range(N + 1)]

for i in range(M):
    A, B, C = list(map(int, input().split()))
    G[A].append((B, C))
    G[B].append((A, C))


def dijkstra(s):
    d = [1 << 28] * (N + 1)
    d[s] = 0
    q = []
    heapq.heappush(q, (0, s))

    while q:
        cur = heapq.heappop(q)

        if d[cur[1]] != cur[0]:
            continue

        for nx in G[cur[1]]:
            if d[nx[0]] > cur[0] + nx[1]:
                d[nx[0]] = cur[0] + nx[1]
                heapq.heappush(q, (cur[0] + nx[1], nx[0]))

    return d


DIRS = [dijkstra(s) for s in RS]
MAT = [[d[r] for r in RS] for d in DIRS]

mem = {}


def solve(idx, st):
    if st == (1 << R) - 1:
        return 0
    if (idx, st) in mem:
        return mem[(idx, st)]

    ret = 1 << 28
    for i in range(R):
        if ((st >> i) & 1) == 0:
            ret = min(ret, solve(i, st | (1 << i)) + MAT[idx][i])

    mem[(idx, st)] = ret
    return ret


print((min([solve(i, 1 << i) for i in range(R)])))


from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
from itertools import permutations
def main():
    N, M, R = list(map(int, input().split()))
    r = list(map(int, input().split()))
    r = [i-1 for i in r]
    l = [[0] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        l[a][b] = c
        l[b][a] = c
    G = csr_matrix(l)
    dd = dijkstra(G, directed=False)
    ans = 10**100
    for i in permutations(r, len(r)):
        t = 0
        for j in range(len(r)-1):
            t += dd[i[j]][i[j+1]]
        ans = min(ans, t)
    return int(ans)
print((main()))


import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, M, R = list(map(int, input().split()))
    r = list([int(x) - 1 for x in input().split()])
    P = permutations(r)

    dp = [[float("inf")] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        dp[a][b] = c
        dp[b][a] = c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                tmp = dp[i][k] + dp[k][j]
                if tmp < dp[i][j]:
                    dp[i][j] = tmp

    ans = float("inf")
    for p in P:
        tmp = 0
        for i in range(R - 1):
            tmp += dp[p[i]][p[i + 1]]

        if tmp < ans:
            ans = tmp

    print(ans)


def __starting_point():
    main()

__starting_point()

import heapq
import itertools
from collections import defaultdict


n, m, r = list(map(int, input().split()))
visiting_town = list(map(int, input().split()))

edges = [[] for i in range(n+1)]
for _ in range(m):
    _from, to, distance = list(map(int, input().split()))
    edges[_from].append([to, distance])
    edges[to].append([_from, distance])


comp_edges = defaultdict(dict)
for _from in visiting_town:
    seen = [False] * (n+1)
    todo = []
    for to, dist in edges[_from]:
        heapq.heappush(todo, [dist, to])

    while todo:
        dist, node = heapq.heappop(todo)
        if seen[node]:
            continue

        seen[node] = dist
        for to, add_dist in edges[node]:
            if seen[to] or to == _from:
                continue
            new_dist = dist + add_dist
            heapq.heappush(todo, [new_dist, to])

    for to in visiting_town:
        if to == _from:
            continue
        comp_edges[_from][to] = seen[to]

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        if to in comp_edges[_from]:
            dist = comp_edges[_from][to]
            result += dist
        else:
            break
    candidates.append(result)

print((min(candidates)))


import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
from itertools import permutations

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m, R = I[:3]
r = I[3:3+R] - 1
a, b, c = I[3+R:].reshape(-1, 3).T
graph = csr_matrix((c, (a-1, b-1)), shape=(n, n))

def main():
    dist = floyd_warshall(graph, directed=False).astype(np.int64)
    
    perms = np.array(list(permutations(r)))
    res = dist[perms[:, :-1], perms[:, 1:]]
    ans = np.amin(np.sum(res, axis=1))
    return ans

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

import itertools
import sys

def main():
  input = sys.stdin.readline
  n, m, r = map(int, input().split())
  R = [int(x) for x in input().split()]
  inf = pow(10, 9)+7

  roads = [[inf]*n for _ in range(n)]
  for i in range(m):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

  for k in range(n):
    for i in range(n):
      for j in range(n):
        if roads[i][j] > roads[i][k]+roads[k][j]:
          roads[i][j] = roads[i][k]+roads[k][j]

  ans = inf
  for value in itertools.permutations(R):
    sub = 0
    for k in range(r-1):
      sub += roads[value[k]-1][value[k+1]-1]
    if ans > sub:
      ans = sub

  print(ans)

def __starting_point():
  main()
__starting_point()

from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
N,M,R = map(int,input().split())

machi = list(map(int,input().split()))

List = [[10**6]*(N) for i in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  
  if List[a-1][b-1] > c:
    List[a-1][b-1] = c
    List[b-1][a-1] = c
G = csgraph_from_dense(List, null_value=10**6)
d = floyd_warshall(G)

import itertools
a = list(itertools.permutations(machi))
arr = []
for i in a:
  ans = 0
  for j in range(R):
    if j != R-1 :
      ans += d[i[j]-1][i[j+1]-1]
  arr.append(ans) 
  
print(int(min(arr)))

from itertools import permutations
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N, M, R = map(int, input().split())
R = list(map(int, input().split()))
A, B, C = np.array([input().split() for _ in range(M)], dtype=int).T
G = csr_matrix((C, (A - 1, B - 1)), shape=(N, N))
path = dijkstra(G, directed=False)
path = (path + 0.5).astype(int)

ans = 10 ** 18
for p in permutations(R):
    cnt = 0
    for x, y in zip(p[:-1], p[1:]):
        x -= 1
        y -= 1
        cnt += path[x][y]
    ans = min(ans, cnt)

print(ans)

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
from itertools import permutations

n,m,R = map(int, input().split())
r = list(map(int, input().split()))
r = [i-1 for i in r]
abc = [list(map(int, input().split())) for i in range(m)]
edge = [[10 ** 9] * (n) for i in range(n)]
for a,b,c in abc:
  a-=1
  b-=1
  edge[a][b] = c
  edge[b][a] = c
d = floyd_warshall(edge)
ans = 10 ** 18
for i in permutations(r):
  tmp = 0
  for j in range(R-1):
    tmp += d[i[j]][i[j+1]]
  ans = min(ans,tmp)
print(int(ans))

from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall

INF = 10 ** 18
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
dp = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    dp[a - 1][b - 1] = c
    dp[b - 1][a - 1] = c

wf = floyd_warshall(dp)
ans = INF
for i in permutations(r):
    tmp = 0
    for j in range(1, len(i)):
        tmp += wf[i[j - 1] - 1][i[j] - 1]
    ans = min(ans, tmp)

print(int(ans))

from itertools import permutations, combinations
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [r[i]-1 for i in range(R)]
vve = [list(map(int,input().split())) for i in range(M)]
v1,v2,edge = zip(*vve)
v1 = list(v1)
v2 = list(v2)
for i in range(M):
  v1[i] -= 1
  v2[i] -= 1
csr = csr_matrix((edge,(v1,v2)),shape = (N,N))
dist = [[0 for j in range(R)] for i in range(R)]
for i,j in combinations(range(R),2):
  r1,r2=r[i],r[j]
  dist[i][j] = int(dijkstra(csr, directed = False,indices = r1)[r2])
  dist[j][i] = dist[i][j]
ans = 10**18
for x in permutations(range(R)):
  distsum = 0
  for i in range(1,R):
    distsum += dist[x[i]][x[i-1]]
  ans = min(ans,distsum)
print(ans)

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

    N,M,R = map(int, input().split())
    r = list(map(int, input().split()))
    for i in range(R):
        r[i] -= 1

    def dijkstra_heap(start,edge):
        #始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf]*N
        used = [False]*N
        d[start] = 0
        used[start] = True
        edgelist = []
        #a:重み(//), b:次の頂点(%)
        for a,b in edge[start]:
            heappush(edgelist,a*(10**6)+b)

        while len(edgelist):
            #まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heappop(edgelist)
            if used[minedge%(10**6)]:
                continue
            node = minedge%(10**6)
            d[node] = minedge//(10**6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist,(e[0]+d[node])*(10**6)+e[1])
        return d

    edge = [[] for i in range(N)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(M):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    kyori = []
    for i in r:
        kyori.append(dijkstra_heap(i,edge))
    
    res = inf
    for i in permutations(range(R), R):
        l = list(i)
        path = 0
        for j in range(R-1):
            path += kyori[l[j]][r[l[j+1]]]
        res = min(res, path)

    print(res)

def __starting_point():
    main()
__starting_point()

from scipy.sparse.csgraph import floyd_warshall
import itertools


def warshal_floyd(d):
    # d[i][j] := iからjへの最短距離
    nonlocal 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])
    # "今現在求まっているiからjへの最短距離"と"今現在求まっているiからkへの最短距離 + 今現在求まっているkからjへの最短距離 の和"を比較する
    return d


N, M, R = list(map(int, input().split()))  # N個の町, M本の道, R個の町を訪れることになった
town = list([int(x)-1 for x in input().split()])
distant = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    distant[a][b] = c
    distant[b][a] = c
for i in range(N):
    distant[i][i] = 0
distant = floyd_warshall(distant)
# warshal_floyd(distant)
# print(distant)  # Rは最大8だから全てを試しても大丈夫
ans = 10**9
for x in itertools.permutations(town):
    x = list(x)
    now = x[0]
    tmp = 0
    for i in range(1, len(x)):
        tmp += distant[now][x[i]]
        now = x[i]
    ans = min(ans, tmp)
print((int(ans)))


from scipy.sparse.csgraph import floyd_warshall
import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
r = [ri-1 for ri in r]

graph = [[0]*N for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  a -= 1; b -= 1
  graph[a][b] = graph[b][a] = c

dist = floyd_warshall(graph).astype(int)
orders = list(itertools.permutations(r, R))

ans = float('inf')
for order in orders:
  d = 0
  for u, v in zip(order, order[1:]):
    d += dist[u][v]
  ans = min(ans, d)

print(ans)

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
import itertools


def main():
    N, M, R = list(map(int, input().split(' ')))
    towns = list(map(lambda t: int(t) - 1, input().split(' ')))
    A = np.zeros((N, N), dtype=int)
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        A[a-1][b-1] = c
        A[b-1][a-1] = c
    fw = floyd_warshall(A)
    d = fw[towns, :][:, towns]
    min_d = 10**12
    for trip in itertools.permutations(range(R)):
        min_d = min([min_d, sum([d[trip[i]][trip[i+1]] for i in range(len(trip) - 1)])])
    print(int(min_d))


def __starting_point():
    main()
__starting_point()

from scipy.sparse.csgraph import floyd_warshall
import numpy as np
from itertools import permutations, combinations
n,m,R = map(int,input().split())
r=list(map(int,input().split()))
for i in range(R):
    r[i]-=1
d = np.zeros((n,n)) 
# 入力
for i in range(m):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    d[a,b] = c
dist =floyd_warshall(d,directed=0).astype(int)
ans=10**10
for v in permutations(r):
    tmp=0
    for i in range(R-1):
        tmp+=dist[v[i],v[i+1]]
    ans=min(ans,tmp)
print(ans)

def main():
    from sys import stdin
    input = stdin.readline
    n, m, r = list(map(int, input().split()))
    root = list(map(int, input().split()))
    abc = [list(map(int, input().split())) for _ in [0]*m]

    import numpy as np
    import scipy.sparse.csgraph as sp
    inf = float('inf')
    d = np.full((n, n), inf)
    for i in range(n):
        d[i][i] = 0
    for a, b, c in abc:
        d[a-1][b-1] = c
        d[b-1][a-1] = c
    # indices=xでxからの単一始点に,return_predecessors=Trueで経路が出る
    s = sp.shortest_path(d)

    from itertools import permutations

    p = list(permutations(root))

    D = 10**10
    for i in p:
        d = 0
        for j in range(len(i)-1):
            d += s[i[j]-1][i[j+1]-1]
        D = min(D, d)
    print((int(D)))


main()


from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from itertools import permutations

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))

g = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    A, B, C = list(map(int, input().split()))
    g[A][B] = C
    g[B][A] = C
g = floyd_warshall(csgraph_from_dense(g))

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += g[p[i]][p[i + 1]]
    result = min(result, t)
print((int(result)))


import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, M, R = list(map(int, input().split()))
    r = list(map(int, input().split()))
    P = permutations(r)

    dp = [[INF] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        dp[a][b] = c
        dp[b][a] = c

    # ワーシャルフロイド
    for k in range(N):
        for i in range(N):
            for j in range(N):
                tmp = dp[i][k] + dp[k][j]
                if tmp < dp[i][j]:
                    dp[i][j] = tmp

    ans = INF
    for p in P:
        tmp = 0
        for i in range(R - 1):
            tmp += dp[p[i] - 1][p[i + 1] - 1]

        if tmp < ans:
            ans = tmp

    print(ans)


def __starting_point():
    main()

__starting_point()

import itertools
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

int1 = lambda x: int(x) - 1

N, M, R = map(int, input().split())
T = sorted(list(map(int1, input().split())))
A = np.array([tuple(map(int, input().split())) for _ in range(M)]).T

matr = csr_matrix((A[2], (A[0] - 1, A[1] - 1)), shape=(N, N))
way = [dijkstra(matr, indices=t, directed=False)[T].astype(int).tolist() for t in T]

ans = float('inf')
for t in itertools.permutations(range(R)):
    tmp = 0
    for i in range(R - 1):
        tmp += way[t[i]][t[i + 1]]
    ans = min(ans, tmp)
print(ans)

import heapq
import itertools

def dijkstra(s):
    inf = pow(10, 10)
    dist = [inf] * (n + 1)
    dist[s] = 0
    c = [0] * (n + 1)
    p = []
    heapq.heapify(p)
    heapq.heappush(p, (dist[s], s))
    while p:
        d, u = heapq.heappop(p)
        if dist[u] < d:
            continue
        c[u] = 1
        for g in G[u]:
            if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
                dist[g[0]] = dist[u] + g[1]
                heapq.heappush(p, (dist[g[0]], g[0]))
    return dist

n, m, r = map(int, input().split())
t = list(map(int, input().split()))
G = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    G[a].append([b, c])
    G[b].append([a, c])
D = [[0] * r for _ in range(r)]
for i in range(r):
    d = dijkstra(t[i])
    for j in range(r):
        D[i][j] = d[t[j]]

x = [i for i in range(r)]
ans = pow(10, 10)
for y in itertools.permutations(x):
    dist = 0
    y = list(y)
    for i in range(r - 1):
        dist += D[y[i]][y[i + 1]]
    ans = min(ans, dist)
print(ans)

from itertools import permutations as perm

def warshall(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]

n,m,r = map(int, input().split())
rr = [i-1 for i in map(int, input().split())]

inf = float('INF')
route = [[inf for j in range(n)] for i in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    route[a-1][b-1] = route[b-1][a-1] = c

warshall(route, n)

ans = inf
for tmp in perm(rr):
    cost = 0
    for i in range(r-1):
        cost += route[tmp[i]][tmp[i+1]]
    if cost < ans:
        ans = cost
print(int(ans))

# coding: utf-8
from heapq import heappop, heappush
from itertools import permutations

N,M,R=map(int,input().split())
town=list(map(int,input().split()))
INF=10**9
G=[[INF for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    A,B,C=map(int,input().split())
    G[A][B]=C
    G[B][A]=C

d=[[INF*10 for i in range(N+1)] for j in range(R)]

for k in range(R):
    r=town[k]
    d[k][r]=0
    
    used=[False for i in range(N+1)]
    
    heap=[]
    heappush(heap,(d[k][r],r))
    
    while heap:
        d_u, u = heappop(heap)

        used[u] = True
        
        if d[k][u] < d_u:
            continue
        
        for v in range(N+1):
            if not(used[v]) and d_u + G[u][v] < d[k][v]:
                d[k][v] = d_u + G[u][v]
                heappush(heap,(d[k][v],v))

ans=INF

L=[i for i in range(R)]

for v in permutations(L,R):
    D=0
    for i in range(R-1):
        D+=d[v[i]][town[v[i+1]]]
    ans=min(ans,D)
    
print(ans)

import itertools
import sys
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
input = sys.stdin.readline


n, m, r = list(map(int, input().split()))
visiting_town = list(map(int, input().split()))
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = list(map(int, input().split()))
    edges[a-1][b-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
comp_dist = {}
for node in visiting_town:
    dist_list = dijkstra(G, directed=False, indices=node-1)
    comp_dist[node-1] = dist_list

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        dist = comp_dist[_from-1][to-1]
        result += dist
    candidates.append(result)

print((int(min(candidates))))


import itertools
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson

N,M,R = map(int, input().split())
r_list = np.array(list(map(int, input().split()))) -1 

nodes = np.full((N,N), np.inf) 
for i in range(M):
    a,b,c = map(int, input().split())
    nodes[a-1,b-1] = nodes[b-1,a-1] = c
min_ds = shortest_path(nodes)
res = 10**9
for cmb in itertools.permutations(r_list):
    prev = cmb[0]
    tmpres = 0
    for to in cmb[1:]:
        tmpres += min_ds[prev,to]
        prev = to
    res = min(res, tmpres)

print(int(res))

import numpy as np
from scipy.sparse.csgraph import dijkstra

N,M,R = list(map(int,input().split()))
r = list(map(int,input().split()))
for i in range(R):
    r[i] -= 1

connections = np.zeros((N,N))
for i in range(M):
    A,B,C = list(map(int,input().split()))
    A,B = A-1,B-1
    
    connections[A][B] = C
    connections[B][A] = C

connections = dijkstra(connections)

def explore(unvisited,total,start):
    if unvisited:
        ret = float('inf')
        for town in unvisited:
            ret = min(ret,explore(unvisited-set([town]),
                total+connections[start][town],town))
        return ret
    else:
        return total

ans = float('inf')
targets = set(r)
for s in r:
    ans = min(ans,explore(targets-set([s]),0,s))
print(int(ans))

def abc073_d():
    from scipy.sparse import lil_matrix
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import permutations

    n, m, r = map(int, input().split())
    R = list(map(lambda x: int(x)-1, input().split()))
    graph = lil_matrix((n, n), dtype=int)
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a, b] = c
        graph[b, a] = c

    dist = floyd_warshall(csgraph=graph)
    #print(dist)

    ans = 10**18
    for route in permutations(R, r):
        tmp = 0
        for i in range(r-1):
            s = route[i]
            t = route[i+1]
            tmp += dist[s][t]
            if tmp > ans: break
        ans = min(ans, tmp)
        #print(route, tmp)

    print(int(ans))

def __starting_point():
    abc073_d()
__starting_point()

from itertools import permutations
import heapq

def dijkstra(N, G, s):
    INF = 10**40
    d = [INF] * N
    d[s] = 0
    q = [(0, s)]
    while q:
        c, v = heapq.heappop(q)
        if d[v] < c:
            continue
        for t, co in G[v]:
            if d[v] + co < d[t]:
                d[t] = d[v] + co
                heapq.heappush(q, (d[t], t))
    return d


def main():
    N, M, _ = list(map(int, input().split()))
    R = list(map(int, input().split()))
    R = [r - 1 for r in R]
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    RM = []
    for r in R:
        d = dijkstra(N, G, r)
        RM.append([d[rr] for rr in R])
    m = 10 ** 40
    for i in permutations(list(range(len(R)))):
        t = i[0]
        c = 0
        for r in i[1:]:
            c += RM[t][r]
            t = r
        m = min(m, c)
    return m


print((main()))


import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense
import itertools

input = sys.stdin.readline


def main():
    N, M, R = [int(x) for x in input().split()]
    r = [int(x) - 1 for x in input().split()]
    ABC = [[int(x) for x in input().split()] for _ in range(M)]

    EDGE = [[10 ** 9] * N for j in range(N)]

    for a, b, c in ABC:
        EDGE[a - 1][b - 1] = c
        EDGE[b - 1][a - 1] = c

    G = csgraph_from_dense(EDGE, null_value=10 ** 9)

    d = floyd_warshall(G)

    ans = float("inf")
    for a in itertools.permutations(r):
        tmp = 0
        c = a[0]
        for n in a:
            tmp += int(d[c][n])
            c = n
        ans = min(ans, tmp)

    print(ans)


def __starting_point():
    main()

__starting_point()

def main():
  import numpy as np
  import itertools
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import dijkstra
  import sys
  readline = sys.stdin.readline
  readlines = sys.stdin.readlines

  N, M, R= map(int, readline().split())
  r = list(map(int,input().split()))
  lines = readlines()
  edge = np.array([line.split() for line in lines], dtype = np.int64).T
  #print(r)
  #print(edge)
  graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
  ans = float("inf")
  distance_mat = {}
  for i in r:
    distance_mat[i-1] = (dijkstra(graph, directed = False, indices = i-1))

  for town in itertools.permutations(r,R):
    #print(town)
    tmp = 0
    for i in range(R-1):
      tmp += distance_mat[town[i]-1][town[i+1]-1]
    ans = min(ans,tmp)
  print(int(ans))
main()

import itertools
def main():
    n,m,r=list(map(int,input().split()))
    rx=[int(i) for i in input().split()]
    inf=100000000
    wf=[[inf]*n for i in range(n)]
    for i in range(n):
        wf[i][i]=0

    for i in range(m):
        a,b,c=list(map(int,input().split()))
        wf[a-1][b-1]=c
        wf[b-1][a-1]=c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if wf[i][j]>wf[i][k]+wf[k][j]:
                    wf[i][j]=wf[i][k]+wf[k][j]
    cnt=0
    l=list(itertools.permutations([i for i in range(r)]))
    cnt=inf
    for i in l:
        cnt_sub=0
        for j in range(r-1):
            cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
        cnt=min(cnt,cnt_sub)
    print(cnt)
main()


from collections import deque
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import itertools

n, m, r = map(int,input().split())
rlist = list(map(int,input().split()))
for i in range(r):
    rlist[i] -= 1
e = np.zeros((n,n), dtype=int)

for i in range(m):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    e[a][b] = c
    e[b][a] = c
csr = csr_matrix(e)
f = floyd_warshall(csr)

ans = 10**18
for v in itertools.permutations(rlist,r):
    d = 0
    for i in range(r-1):
        d += f[v[i]][v[i+1]]
    ans = min(ans, d)
print(int(ans))

def main():
    from sys import stdin
    input = stdin.readline

    n, m, r = list(map(int, input().split()))
    l = [int(i) - 1 for i in input().split()]
    d = [[10**8] * n for _ in range(n)]
    for _ in range(m):
        i, j, k = list(map(int, input().split()))
        d[i-1][j-1] = k
        d[j-1][i-1] = k

    # Warshall-Floyd algorithm
    for k in range(n):
        for i in range(n-1):
            for j in range(i+1, n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    d[j][i] = d[i][j]

    # full search
    # 8! = 40320
    from itertools import permutations

    answer = float('inf')
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += d[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()


from scipy.sparse.csgraph import shortest_path
import numpy as np
import itertools

N,M,R = list(map(int,input().split()))
r = list(map(int, input().split()))

edge = np.zeros((N+1,N+1))
for _ in range(M):
  A,B,C = list(map(int,input().split()))
  edge[A,B] = C  
dist = shortest_path(edge, directed = False).astype(int)

answer = 10**18
for visit in itertools.permutations(r):
  p = 0
  prev = visit[0]
  for x in visit[1:]:
    if prev != None:
      p += dist[prev,x]
    prev = x
  answer = min(answer,p)
  
print(answer)


from scipy.sparse.csgraph import floyd_warshall
import numpy as np
from itertools import permutations

n,m,r = map(int,input().split())
rr = np.array(list(map(int,input().split()))) - 1

L = np.zeros((n,n),int)
for _ in range(m):
    a,b,c = map(int,input().split())
    L[a-1,b-1] = c

shortest = floyd_warshall(L, directed = False)

ans = float('inf')

for route in permutations(rr,len(rr)):
    ans = min(ans, shortest[route[:-1],route[1:]].sum())
print(int(ans))

# ワーシャルフロイドで、各町間の最短距離の更新は200^3 = 8,000,000
# 訪れるべき町Rはたかだか8個なので、順番の全通りを試して8! = 約40000通り

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall
from scipy.sparse import csr_matrix

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = list(map(lambda x:x-1,r))

E = [[0 for j in range(N)] for i in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  E[a-1][b-1] = c
  E[b-1][a-1] = c

E = np.array(E)
E = shortest_path(E,method = "FW")

# DFSですべての数を試す
stack = []
for i in range(len(r)):
  stack.append([r[i],[],0])
ans = 10 ** 18
while stack:
  v,visited,dist = stack.pop()
  if len(visited) != 0:
    dist += E[visited[-1]][v]
  visited2 = visited.copy()
  visited2.append(v)
  if len(visited2) == len(r):
    if dist < ans:
      ans = dist
    continue
  for i in range(len(r)):
    if r[i] not in visited2:
      stack.append([r[i],visited2,dist])
    
print(int(ans))

from sys import stdin
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense
def main():
    #入力
    readline=stdin.readline
    inf=10**9
    n,m,r=map(int,readline().split())
    targets=list(map(lambda x:int(x)-1,readline().split()))
    G=[[inf]*n for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,readline().split())
        a-=1
        b-=1
        G[a][b]=min(G[a][b],c)
        G[b][a]=min(G[b][a],c)

    #ワーシャルフロイド
    G=csgraph_from_dense(G,null_value=10**9)
    li=floyd_warshall(G)
    li=[list(map(int,li[i])) for i in range(n)]
    
    #順列全探索
    ans=inf
    for p in permutations(targets,r):
        tmp=0
        for i in range(r-1):
            now=p[i]
            nex=p[i+1]
            tmp+=li[now][nex]
        ans=min(ans,tmp)

    print(ans)

def __starting_point():
    main()
__starting_point()

from itertools import *
from scipy.sparse.csgraph import *
import numpy as np
N,M,R = map(int,input().split())
T = list(map(int,input().split()))
E = [list(map(int,input().split())) for m in range(M)]
G = np.zeros((N,N))
A = []

for a,b,c in E:
  G[a-1][b-1] = c
  G[b-1][a-1] = c

F = floyd_warshall(G)

for P in permutations(T):
  A+=[sum(F[P[r]-1][P[r+1]-1] for r in range(R-1))]

print(int(min(A)))

from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n,m,r=nii()
r=list(nii())

s=[[float('inf')]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    s[i][j]=0
for i in range(m):
  a,b,c=nii()
  a-=1
  b-=1
  s[a][b]=c
  s[b][a]=c

ws=floyd_warshall(s)

ans=10**9
for i in permutations(r):
  t_ans=0
  for j in range(1,len(i)):
    t_ans+=ws[i[j-1]-1][i[j]-1]
  ans=min(ans,t_ans)
print(int(ans))

import itertools
from scipy.sparse.csgraph import floyd_warshall

N, M, R = map(int, input().split())
r = tuple(map(int, input().split()))

INF = 10**10

d = [[INF] * N for _ in range(N)]

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

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c


def warshall(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]


# d = floyd_warshall(d)
warshall(d)


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]-1][p[i+1]-1]

    if ans > dist:
        ans = dist

print(int(ans))

from itertools import permutations as perm
from scipy.sparse.csgraph import dijkstra as di

def warshall(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]

n,m,r = list(map(int, input().split()))
rr = [i-1 for i in map(int, input().split())]

inf = float('INF')
route = [[0 for j in range(n)] for i in range(n)]
for _ in range(m):
    a,b,c = list(map(int, input().split()))
    route[a-1][b-1] = route[b-1][a-1] = c

route = di(route, n)

ans = inf
for tmp in perm(rr):
    cost = 0
    for i in range(r-1):
        cost += route[tmp[i]][tmp[i+1]]
    if cost < ans:
        ans = cost
print((int(ans)))


from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
N, M, R = list(map(int, input().split()))
r = tuple(map(int, input().split()))

inf = 10**9
graph = np.ones((N, N), dtype=int)*inf
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
fy = floyd_warshall(graph)

ans = 10 ** 9
for p in permutations(r):
    tmp = 0
    for x, y in zip(p[:-1], p[1:]):
        x -= 1
        y -= 1
        tmp += int(fy[x][y])
    ans = min(ans, tmp)
print(ans)


from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
l=[[float('inf')]*n for _ in range(n)]
for _ in range(m):
    a,b,c,=map(int,input().split())
    a-=1
    b-=1
    l[a][b]=c
    l[b][a]=c
for i in range(n):
    l[i][i] = 0 #自身のところに行くコストは０
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
#F=warshall_floyd(l)
F1 = floyd_warshall(l)
ans=float('inf')
for v in permutations(R):
    temp=0
    for i in range(r-1):
        temp+=F1[v[i]-1][v[i+1]-1]
    ans=min(ans,temp)
print(int(ans))

# coding: utf-8
# Your code here!

#保存
import heapq
import sys
import itertools
 
sys.setrecursionlimit(10**7)

def bfs(cost,node):
    root[node]=min(root[node],cost)
    for next_c,next_n in way[node]:
        if root[next_n]==10**9:
            heapq.heappush(q,[cost+next_c,next_n])
    return
    
N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))

way=[[] for i in range(N)]

for _ in range(M):
    A,B,C=list(map(int,input().split()))
    way[A-1].append([C,B-1])
    way[B-1].append([C,A-1])

made=[]

#print(q)
for start in r:
    root=[10**9]*N
    q=[[0,start-1]]
    heapq.heapify(q)#costとnode
    while q:
        temp=heapq.heappop(q)
        #print(temp)
        if root[temp[1]]==10**9:
            bfs(temp[0],temp[1])
    made.append(root)
#print(made)

ans=10**9
for order in itertools.permutations([i for i in range(len(r))]):
    #print(order)
    temp=0
    for i in range(len(order)-1):
        fro=r[order[i]]
        aft=r[order[i+1]]
        #print("YES")
        #print(order[i]-1,order[i+1]-1)
        #print(root[order[i]-1][0])
        temp+=abs(made[order[i]][aft-1]-made[order[i]][fro-1])
    ans=min(ans,temp)
print(ans)




import time
import itertools

def main():
    N,M,R = tuple([int(x) for x in input().split()])

    r = [int(x)-1 for x in input().split()]
    
    w_e = [tuple([int(x)for x in input().split()]) for _ in [0]*M]
    w_e = [(a-1,b-1,w) for (a,b,w) in w_e]


    g = Graph(list(range(N)),w_e)

    minimums = {}
    for r_i in r:
        minimums[r_i] = g.dijkstra(r_i)[0]

    bf = itertools.permutations(r)

    candidates = []
    for bf_i in bf:
        distance = 0
        for i in range(R-1):
            distance += minimums[bf_i[i]][bf_i[i+1]]
        candidates.append(distance)

    print(min(candidates))

def speedtest(func,*args):
    b = time.perf_counter()
    res = func(*args)
    e = time.perf_counter()
    elapsed = e-b
    print("{} (sec)".format(elapsed))

    return res

class Graph:
    def __init__(self,w_v,w_e):
        super().__init__()
        self.size = len(w_v)
        self.w_v = [v_i for v_i in w_v]#value of vartex
        self.w_e = [{} for _ in [0]*self.size]

        self.neighbor = [[] for _ in [0]*self.size]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i#weight of edge
            self.w_e[b_i][a_i] = w_i#weight of edge

            self.neighbor[a_i].append(b_i)
            self.neighbor[b_i].append(a_i)

    def dijkstra(self,v_n):
        d = [-1]*self.size
        temp_d = [(10**9,i)for i in range(self.size)]
        temp_d[v_n] = (0,v_n)
        prev = [-1]*self.size

        q = set(range(self.size))
        
        while len(q)>0:
            u = min([temp_d[q_i] for q_i in q])[1]
            d[u] = temp_d[u][0]
            q.discard(u)
            for v in self.neighbor[u]:
                temp = temp_d[u][0]+self.w_e[u][v]
                if temp_d[v][0]>temp:
                    temp_d[v] = temp,v
                    prev[v] = u

        return d,prev

def __starting_point():
    main()
__starting_point()

from itertools import permutations
import sys
input = sys.stdin.readline

def main():
    N, M, RR = map(int, input().split())
    R = list(map(int, input().split()))
    INF = float("inf")
    T = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = tuple(map(int, input().split()))
        T[a-1][b-1] = c
        T[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if T[i][j] > T[i][k]+T[k][j]:
                    T[i][j] = T[i][k]+T[k][j]
    print(min(sum(T[rs[i]-1][rs[i+1]-1] for i in range(RR-1)) for rs in permutations(R)))

def __starting_point():
    main()
__starting_point()

from scipy.sparse.csgraph import dijkstra
import numpy as np
from itertools import permutations
N,M,R = list(map(int,input().split()))
r = list(map(int,input().split()))

"""
https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
"""

def warshall_floyd(d):
    n = len(d)
    #d[i][j]: iからjへの最短距離
    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

graph = [[float("inf") for i in range(N)] for j in range(N)] 
for i in range(M):
    A,B,C = list(map(int,input().split()))
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C

dist = dijkstra(graph)

ans = 1e10
for i in permutations(r):
    flag = True
    way = list(i)
    tmp = 0
    for i in range(len(way)-1):
        if dist[way[i]-1][way[i+1]-1] < 0:
            flag = False
            break
        tmp += dist[way[i]-1][way[i+1]-1]
    if flag:
        ans = min(tmp,ans)

print((int(ans)))


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

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

stdin = sys.stdin

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

N, M, R = na()
r = na()
g = [[0] * N for _ in range(N)]
for i in range(M):
    a, b, c = na()
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

g = np.array(g)
d = shortest_path(g)

R = len(r)
ans = inf
for x in itertools.permutations(r):
    tmp = 0
    for i in range(R-1):
        tmp += d[x[i] - 1][x[i+1] - 1]
    ans = min(ans, tmp)
print((int(ans)))






import itertools
import sys
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
input = sys.stdin.readline


n, m, r = list(map(int, input().split()))
visiting_town = list(map(int, input().split()))
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = list(map(int, input().split()))
    edges[a-1][b-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
comp_dist = dijkstra(G, directed=False)

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        dist = comp_dist[_from-1][to-1]
        result += dist
    candidates.append(result)

print((int(min(candidates))))


from itertools import permutations
import numpy as np
from scipy.sparse.csgraph import dijkstra

with open(0) as f:
    N, M, R = map(int, f.readline().split())
    r = list(map(int, f.readline().split()))
    path = [tuple(map(int, line.split())) for line in f.readlines()]

graph = np.full((N,N), np.inf)
for a, b, c in path:
    graph[a-1, b-1] = c
    graph[b-1, a-1] = c

graph = dijkstra(graph, directed=False)
ans = np.inf
permutation = list(permutations(r))
for p in permutation:
    way = 0
    for x,y in zip(p[:len(r)], p[1:]):
        way += graph[x-1, y-1]
    ans = min(ans, way)
print(int(ans))

n,m,r  = list(map(int,input().split()))
r_list = list(map(int,input().split()))
matrix = [[float("inf") for i in range(n)] for j in range(n)]
for c in range(n):
  matrix[c][c] = 0
for v in range(m):
  a,b,c = list(map(int,input().split()))
  if matrix[a-1][b-1] > c:
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c
import numpy as np
matrix = np.array(matrix)
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
load = shortest_path(matrix, directed=False)
import itertools
ans_list = []
for balls in itertools.permutations(r_list):
    balls = list(balls)
    ans = 0
    for i in range(1,len(r_list)):
      ans += load[balls[i-1]-1][balls[i]-1]
    ans_list.append(int(ans))
    
print((min(ans_list)))
      




N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]

dist = [[10e8 for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    dist[a-1][b-1] = dist[b-1][a-1] = c 
del a, b, c, K

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

def mindist(x, X):
    nonlocal dist
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y] + mindist(y,Y) for y in Y])

ans = min([mindist(r, R) for r in R])
print(ans)

from itertools import permutations
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
inf = 10 ** 10
n, m, r = map(int,input().split())
R = list(map(int,input().split()))

edge = [[inf] * n for i in range(n)]
for i in range(m):
    a, b, c = map(int,input().split())
    edge[a - 1][b - 1] = c

G = csgraph_from_dense(edge, null_value = inf)
d = floyd_warshall(G, False)

rec = inf
for i in permutations(R, r):
    temp = 0
    #print(i)
    for j in range(r):
        if j == r - 1:continue
        temp += d[i[j] - 1][i[j + 1] - 1]
    rec = min(rec, temp)

print(int(rec))