from scipy.sparse import*

from itertools import permutations as pm



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

r = [int(i) for i in input().split()]



u,v,l = list(zip(*[list(map(int,input().split())) for i in range(m)]))



A=csgraph.dijkstra(csr_matrix((l,(u,v)),(n+1,n+1)),0)



s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))

print((int(s)))

from scipy.sparse import*

from itertools import permutations as pm



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

r = [int(i) for i in input().split()]



u,v,l = list(zip(*[list(map(int,input().split())) for i in range(m)]))



A=csgraph.dijkstra(csr_matrix((l,(u,v)),[n+1]*2),0)



s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))

print((int(s)))

from scipy.sparse import *
from itertools import permutations as pm

n, m, h = list(map(int, input().split()))
r = [int(i) for i in input().split()]
u, v, l = list(zip(*[list(map(int, input().split())) for i in range(m)]))
A = csgraph.dijkstra(csr_matrix((l, (u, v)), (n + 1, n + 1)), 0)
s = min(sum(A[i][j] for i, j in zip(a[:-1], a[1:])) for a in pm(r))
print((int(s)))

from scipy.sparse import *
from itertools import permutations as pm

n, m, h = list(map(int, input().split()))
r = [int(i) for i in input().split()]
u, v, l = list(zip(*[list(map(int, input().split())) for i in range(m)]))
A = csgraph.dijkstra(csr_matrix((l, (u, v)), [n + 1] * 2), 0)
s = min(sum(A[i][j] for i, j in zip(a[:-1], a[1:])) for a in pm(r))
print((int(s)))

-A = csgraph.dijkstra(csr_matrix((l, (u, v)), (n + 1, n + 1)), 0) +A = csgraph.dijkstra(csr_matrix((l, (u, v)), [n + 1] * 2), 0)