AtCoder Beginner Contest 073 - joisino's travel

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: MEDIUM

Starter code:

Solutions:
(n, m, R) = list(map(int, input().split()))
r = list(map(int, input().split()))
dp = [[float('INF')] * n for i in range(n)]
for i in range(m):
	(a, b, c) = list(map(int, input().split()))
	dp[a - 1][b - 1] = c
	dp[b - 1][a - 1] = c
for i in range(n):
	dp[i][i] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
from itertools import permutations
per = list(permutations(r, R))
ans = float('INF')
for tup in per:
	ans_kouho = 0
	for i in range(R - 1):
		ans_kouho = ans_kouho + dp[tup[i] - 1][tup[i + 1] - 1]
	ans = min(ans, ans_kouho)
print(ans)


from collections import deque
import itertools
INF = 10 ** 12 + 7
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
d = [[INF] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(A, B, C) = map(int, input().split())
	d[A][B] = C
	d[B][A] = C
for i in range(1, N + 1):
	d[i][i] = 0
for k in range(N + 1):
	for i in range(N + 1):
		for j in range(N + 1):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = INF
for i in itertools.permutations(r, len(r)):
	val = 0
	for j in range(1, len(r)):
		val += d[i[j - 1]][i[j]]
	ans = min(ans, val)
print(ans)


import itertools
(n, m, R) = map(int, input().split())
r = list(map(int, input().split()))
d = [[10 ** 10 for j in range(n)] for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	d[a][b] = c
	d[b][a] = c
for i in range(n):
	d[i][i] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			d[i][j] = min(d[i][k] + d[k][j], d[i][j])
ans = 10 ** 10
for i in itertools.permutations(r):
	x = i
	k = 0
	for j in range(R - 1):
		(a, b) = (x[j + 1], x[j])
		a -= 1
		b -= 1
		k += d[b][a]
	ans = min(ans, k)
print(ans)


import itertools
(n, m, r) = map(int, input().split())
R = list(map(int, input().split()))
DP = [[10 ** 10 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
	DP[i][i] = 0
for _ in range(m):
	(a, b, c) = map(int, input().split())
	DP[a][b] = c
	DP[b][a] = c
for k in range(1, n + 1):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j])
ans = 10 ** 10
for permutation in itertools.permutations(R, r):
	dist = 0
	for i in range(r - 1):
		dist += DP[permutation[i]][permutation[i + 1]]
	ans = min(ans, dist)
print(ans)


import itertools
(N, M, R) = map(int, input().split())
r = [int(s) - 1 for s in input().split()]
(a, b, c) = ([0] * M, [0] * M, [0] * M)
for i in range(M):
	(a[i], b[i], c[i]) = map(int, input().split())
	a[i] -= 1
	b[i] -= 1
wf = [[float('inf')] * N for _ in range(N)]
for i in range(M):
	wf[a[i]][b[i]] = c[i]
	wf[b[i]][a[i]] = c[i]
for (k, i, j) in itertools.product(range(N), repeat=3):
	wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
x = float('inf')
for route in itertools.permutations(r):
	y = sum((wf[route[i]][route[i + 1]] for i in range(R - 1)))
	x = min(x, y)
print(x)


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


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


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)


import itertools
(N, M, R) = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
ABC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 7
d = [[INF] * N for _ in range(N)]
for (A, B, C) in ABC:
	d[A - 1][B - 1] = C
	d[B - 1][A - 1] = C
for k in range(N):
	for i in range(N):
		for j in range(i + 1, N):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
			d[j][i] = d[i][j]
ans = INF * M
for r in itertools.permutations(r):
	S = 0
	for (i, ri) in enumerate(r[:-1]):
		S += d[ri][r[i + 1]]
	ans = min(ans, S)
print(ans)


from itertools import *
(n, m, o) = map(int, input().split())
(*R,) = map(int, input().split())
INF = float('inf')
d = [[INF] * n for _ in range(n)]
r = range
for i in r(n):
	d[i][i] = 0
for _ in r(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = d[b - 1][a - 1] = c
for k in r(n):
	for i in r(n):
		for j in r(n):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
v = [[d[i - 1][j - 1] for j in R] for i in R]
m = INF
for t in permutations(r(o)):
	a = 0
	f = 1
	for (i, j) in zip(t, t[1:]):
		if v[i][j] == INF:
			f = 0
			break
		else:
			a += v[i][j]
	if f:
		m = min(m, a)
print(m)


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 itertools
(N, M, R) = map(int, input().split())
r = map(int, input().split())
A = [[1 << 64] * N for _ in range(N)]
for i in range(N):
	A[i][i] = 0
for _ in range(M):
	(a, b, c) = map(int, input().split())
	A[a - 1][b - 1] = A[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			A[i][j] = min(A[i][j], A[i][k] + A[k][j])
res = 1 << 64
for perm in itertools.permutations([x - 1 for x in r]):
	cost = 0
	for i in range(R - 1):
		cost += A[perm[i]][perm[i + 1]]
	if cost < res:
		res = cost
print(res)


import numpy as np
from scipy.sparse.csgraph import floyd_warshall
(n, m, r) = map(int, input().split())
R = list(map(int, input().split()))
d = np.array([[float('inf') for i in range(n)] for i in range(n)])
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))


(n, m, r) = map(int, input().split())
road = list(map(int, input().split()))
cost = [[float('inf')] * n for i in range(n)]
for i in range(n):
	cost[i][i] = 0
for i in range(m):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	cost[a][b] = c
	cost[b][a] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
import itertools
ans = float('inf')
for i in itertools.permutations(road):
	tmp = 0
	for j in range(len(i) - 1):
		tmp += cost[i[j] - 1][i[j + 1] - 1]
	if tmp < ans:
		ans = tmp
print(ans)


from itertools import permutations
(N, M, R) = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a][b] = c
	G[b][a] = c
for k in range(N):
	G[k][k] = 0
	for i in range(N):
		for j in range(N):
			G[i][j] = min(G[i][j], G[i][k] + G[k][j])
ans = float('inf')
for perm in permutations(r):
	tmp = 0
	for i in range(R - 1):
		tmp += G[perm[i]][perm[i + 1]]
	ans = min(ans, tmp)
print(ans)


import itertools
(N, M, R) = map(int, input().split())
INF = 2 ** 63 - 1
d = [[INF for i in range(N + 1)] for j in range(N + 1)]
r = list(map(int, input().split()))
r = list(itertools.permutations(r))
for i in range(M):
	(a, b, c) = map(int, input().split())
	d[a][b] = c
	d[b][a] = c
for i in range(N + 1):
	d[i][i] = 0
for k in range(N + 1):
	for i in range(N + 1):
		for j in range(N + 1):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = INF
for path in r:
	anstemp = 0
	for i in range(R - 1):
		anstemp += d[path[i]][path[i + 1]]
	ans = min(anstemp, ans)
print(ans)


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 itertools import permutations
import sys
input = sys.stdin.readline
(N, M, R) = map(int, input().split())
dest = [x - 1 for x in map(int, input().split())]
inf = float('inf')
mat = [[inf] * N for _ in range(N)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	mat[a - 1][b - 1] = mat[b - 1][a - 1] = c
for i in range(N):
	for j in range(N):
		for k in range(N):
			mat[j][k] = min(mat[j][k], mat[j][i] + mat[i][k])
ans = inf
for l in permutations(dest):
	tmp = 0
	for (u, v) in zip(l, l[1:]):
		tmp += mat[u][v]
	ans = min(ans, tmp)
print(ans)


from itertools import permutations
(n, m, rl) = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('inf') for _ in range(n)] for _ in range(n)]
for i in range(m):
	(x, y, z) = map(int, input().split())
	(d[x - 1][y - 1], d[y - 1][x - 1]) = (z, z)
for i in range(n):
	d[i][i] = 0
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])
a = float('inf')
for i in permutations(r, rl):
	aa = 0
	for j in range(rl - 1):
		aa += d[i[j] - 1][i[j + 1] - 1]
	a = min(a, aa)
print(a)


import itertools
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
m = [[10 ** 10] * N for i in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	m[a - 1][b - 1] = c
	m[b - 1][a - 1] = c
for i in range(N):
	m[i][i] = 0
for i in range(N):
	for j in range(N):
		for k in range(N):
			m[j][k] = min(m[j][k], m[j][i] + m[i][k])
ans = 10 ** 10
for l in itertools.permutations(r):
	cost = 0
	for i in range(1, R):
		cost += m[l[i - 1] - 1][l[i] - 1]
	ans = min(ans, cost)
print(ans)


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 sys
from itertools import permutations as per
input = sys.stdin.readline
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('inf')] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
	d[i][i] = 0
for _ in range(M):
	(a, b, c) = map(int, input().split())
	d[a][b] = c
	d[b][a] = c
for k in range(1, N + 1):
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			d[i][j] = min(d[i][k] + d[k][j], d[i][j])
res = float('inf')
for p in per(r, R):
	t = 0
	for i in range(R - 1):
		t += d[p[i]][p[i + 1]]
	res = min(t, res)
print(res)


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


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


import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
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
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
graph = csr_matrix(dist_matrix)
dist_matrix = floyd_warshall(graph, directed=False)
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))


from itertools import permutations
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
r = permutations(r, len(r))
INF = 10 ** 10
dist = [[INF] * N for _ in range(N)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	dist[a - 1][b - 1] = dist[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			if dist[i][j] > dist[i][k] + dist[k][j]:
				dist[i][j] = dist[j][i] = dist[i][k] + dist[k][j]
ans = INF
for i in r:
	tmp = 0
	for j in range(len(i) - 1):
		tmp += dist[i[j] - 1][i[j + 1] - 1]
	ans = min(ans, tmp)
print(ans)


import itertools
(n, m, r) = map(int, input().split())
wa = [[float('INF')] * n for i in range(n)]
l = [i - 1 for i in map(int, input().split())]
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	wa[a][b] = c
	wa[b][a] = c
for i in range(n):
	wa[i][i] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			wa[i][j] = min(wa[i][j], wa[i][k] + wa[k][j])
ans = float('INF')
for p in list(itertools.permutations(l)):
	count = 0
	for i in range(r - 1):
		count += wa[p[i]][p[i + 1]]
	ans = min(ans, count)
print(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()


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):
	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 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 sys, copy
from itertools import permutations

def wf(d):
	for k in range(N):
		for i in range(N):
			for j in range(N):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
(N, M, R) = map(int, input().split())
Rs = list(map(int, input().split()))
d = [[float('inf') for i in range(N)] for i in range(N)]
for _ in range(M):
	(a, b, c) = map(int, sys.stdin.readline().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
for i in range(N):
	d[i][i] = 0
wf(d)
ans = float('inf')
for prm in permutations(Rs, R):
	ans = min(ans, sum([d[prm[i - 1] - 1][prm[i] - 1] for i in range(1, R)]))
print(ans)


from itertools import permutations
INF = 10 ** 18
(n, m, r) = map(int, input().split())
dist = [[INF for _ in range(n + 1)] for _ in range(n + 1)]
dp = [[-1 for _ in range(r + 1)] for _ in range((1 << r) + 1)]
r_t = list(map(int, input().split()))
for i in range(n + 1):
	dist[i][i] = 0
for _ in range(m):
	(a, b, c) = map(int, input().split())
	dist[a][b] = c
	dist[b][a] = c
for k in range(n + 1):
	for i in range(n + 1):
		for j in range(n + 1):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
r_list = list(permutations(r_t))
fans = INF
for i in r_list:
	ans = 0
	for j in range(r - 1):
		ans += dist[i[j + 1]][i[j]]
	fans = min(fans, ans)
print(fans)


from itertools import permutations
inf = 10 ** 9
(n, m, R) = map(int, input().split())
r = list(map(int, input().split()))
rr = permutations(r, R)
dis = [[inf] * n for _ in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	dis[a - 1][b - 1] = c
	dis[b - 1][a - 1] = c
for i in range(n):
	for j in range(n):
		for k in range(n):
			dis[j][k] = min(dis[j][i] + dis[i][k], dis[j][k])
ans = 10 ** 12
for x in rr:
	e = 0
	for i in range(R - 1):
		e += dis[x[i + 1] - 1][x[i] - 1]
	ans = min(ans, e)
print(ans)


(n, m, R) = [int(x) for x in input().split()]
r = [int(x) - 1 for x in input().split()]
d = [[float('inf') for _ in [0] * n] for _ in [0] * n]
for i in range(n):
	d[i][i] = 0
for i in [0] * m:
	(a, b, c) = [int(x) for x in input().split()]
	d[a - 1][b - 1] = d[b - 1][a - 1] = c
from itertools import product, permutations
for (k, i, j) in product(range(n), range(n), range(n)):
	if d[i][j] > d[i][k] + d[k][j]:
		d[i][j] = d[i][k] + d[k][j]

def Long(args):
	ans = 0
	for i in range(len(args) - 1):
		ans += d[args[i + 1]][args[i]]
	return ans
print(min((Long(i) for i in permutations(r))))


import itertools
(n, m, r_) = map(int, input().split())
r = list(map(int, input().split()))
for i in range(r_):
	r[i] -= 1
d = [[10 ** 10 for _ in range(n)] for i in range(n)]
for i in range(m):
	(ai, bi, ci) = map(int, input().split())
	ai -= 1
	bi -= 1
	d[ai][bi] = d[bi][ai] = ci
for k in range(n):
	for i in range(n):
		for j in range(n):
			d[i][j] = min(d[i][k] + d[k][j], d[i][j])
ans = 10 ** 10
for l in itertools.permutations(r, r_):
	tmp = 0
	for i in range(r_ - 1):
		tmp += d[l[i]][l[i + 1]]
	ans = min(ans, tmp)
print(ans)


(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):
	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)


import itertools
(n, m, R) = map(int, input().split())
r = list(map(int, input().split()))
INF = 10 ** 10
d = [[INF for i in range(n)] for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = 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])
for i in range(R):
	r[i] -= 1
res = INF
for rp in itertools.permutations(r):
	tres = 0
	for i in range(R - 1):
		tres += d[rp[i]][rp[i + 1]]
	res = min(res, tres)
print(res)


from itertools import permutations
(n, m, r) = map(int, input().split())
R = list(map(int, input().split()))
inf = 10 ** 9
edges = [[inf for i in range(n + 1)] for i in range(n + 1)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	edges[a][b] = c
	edges[b][a] = c
for k in range(1, n + 1):
	for i in range(1, n):
		for j in range(i, n + 1):
			if edges[i][j] > edges[i][k] + edges[k][j]:
				edges[i][j] = edges[i][k] + edges[k][j]
				edges[j][i] = edges[i][j]
ans = inf
for i in permutations(R):
	tmp = 0
	for j in range(r - 1):
		tmp += edges[i[j]][i[j + 1]]
	ans = min(tmp, ans)
print(ans)


(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
dp = [[10 ** 9] * N for _ in range(N)]
for _ in range(M):
	(A, B, C) = map(int, input().split())
	A -= 1
	B -= 1
	dp[A][B] = C
	dp[B][A] = C
for z in range(N):
	for x in range(N):
		for y in range(N):
			dp[x][y] = min(dp[x][y], dp[x][z] + dp[z][y])
import itertools
ans = 10 ** 9
for p in itertools.permutations(range(R)):
	t = 0
	rp = [r[i] for i in p]
	for i in range(R - 1):
		t += dp[rp[i] - 1][rp[i + 1] - 1]
	ans = min(ans, t)
print(ans)


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


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
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
inf = float('inf')
mat = [[inf] * N for _ in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	if mat[a - 1][b - 1] > c:
		mat[a - 1][b - 1] = mat[b - 1][a - 1] = c
for i in range(R):
	r[i] -= 1
ans = inf
for k in range(N):
	for i in range(N):
		for j in range(N):
			mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])
for rr in itertools.permutations(r, R):
	t_sum = 0
	for j in range(1, R):
		t_sum += mat[rr[j - 1]][rr[j]]
	ans = min(ans, t_sum)
print(int(ans))


import itertools
(n, m, r) = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
d = [[10 ** 18] * n for j in range(n)]
for i in range(n):
	d[i][i] = 0
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	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])
ans = 10 ** 18
for p in itertools.permutations(t):
	now = 0
	for i in range(r - 1):
		now += d[p[i] - 1][p[i + 1] - 1]
	ans = min(ans, now)
print(ans)


from itertools import permutations
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
Ans = 10 ** 10
A = [[10 ** 10 for _ in range(N)] for _ in range(N)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	A[a - 1][b - 1] = c
	A[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			A[i][j] = min(A[i][j], A[i][k] + A[k][j])
P = list(permutations(r))
for p in P:
	d = 0
	for i in range(R - 1):
		d += A[p[i] - 1][p[i + 1] - 1]
	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 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))


from itertools import permutations
(n, m, R) = map(int, input().split())
r = [int(i) - 1 for i in input().split()]
INF = float('INF')
d = [[INF] * n for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	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])
ans = INF
for p in permutations(r):
	res = 0
	for i in range(R - 1):
		res += d[p[i]][p[i + 1]]
	ans = min(ans, res)
print(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()


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

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	M = int(next(tokens))
	R = int(next(tokens))
	r = [int(next(tokens)) for _ in range(R)]
	A = [int()] * M
	B = [int()] * M
	C = [int()] * M
	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():
	main()
__starting_point()


from itertools import permutations
inf = float('inf')
(n, m, r) = map(int, input().split())
t = tuple((int(x) - 1 for x in input().split()))
g = [[inf] * n for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	g[a][b] = c
	g[b][a] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = inf
for p in permutations(t):
	ans = min(ans, sum((g[a][b] for (a, b) in zip(p, p[1:]))))
print(ans)


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


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
(N, M, R) = map(int, input().split())
INF = 10 ** 9
d = [[INF] * N for i in range(N)]
r = list(map(int, input().split()))
for i in range(M):
	(A, B, C) = map(int, input().split())
	d[A - 1][B - 1] = C
	d[B - 1][A - 1] = 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])
ans = 10 ** 9
for L in permutations(r):
	temp = 0
	for j in range(R - 1):
		temp += d[L[j] - 1][L[j + 1] - 1]
	ans = min(temp, ans)
print(ans)


(N, M, K) = (int(x) for x in input().split())
R = [int(x) - 1 for x in input().split()]
dist = [[1000000000.0 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
(n, m, r) = map(int, input().split())
R = list(map(lambda x: int(x) - 1, input().split()))
INF = 10 ** 18
dist = [[INF] * n for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	dist[a - 1][b - 1] = c
	dist[b - 1][a - 1] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])
ans = INF
for subset in permutations(R):
	d = 0
	for (v, v2) in zip(subset, subset[1:]):
		d += dist[v][v2]
	if d < ans:
		ans = d
print(ans)


import itertools
import sys
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
W = [[10 ** 10 for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	(W[a][b], W[b][a]) = (c, c)
for k in range(N + 1):
	for i in range(N + 1):
		for j in range(N + 1):
			W[i][j] = min(W[i][j], W[i][k] + W[k][j])
answer = 10 ** 10
for v in itertools.permutations(r, R):
	tmp = 0
	for i in range(1, R):
		tmp += W[v[i]][v[i - 1]]
	answer = min(answer, tmp)
print(answer)


import itertools
(n, m, r) = map(int, input().split())
rr = list(map(int, input().split()))
inf = 10000000000
g = [[inf for i in range(n)] for j in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	g[a - 1][b - 1] = c
	g[b - 1][a - 1] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = 10 ** 10
for i in itertools.permutations(range(0, r), r):
	kai = 0
	for j in range(r - 1):
		kai += g[rr[i[j]] - 1][rr[i[j + 1]] - 1]
	ans = min(ans, kai)
print(ans)


from itertools import permutations
(n, m, r) = list(map(int, input().split()))
rlst = list(map(int, input().split()))
inf = 10 ** 20
d = [[inf] * (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
for k in range(1, n + 1):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = inf
for comb in permutations(rlst, r):
	i = 0
	tans = 0
	while i + 1 < r:
		tans += d[comb[i]][comb[i + 1]]
		i += 1
	ans = min(ans, tans)
print(ans)


import itertools, math
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
adj = [[float('inf')] * (N + 1) for _ in range(N + 1)]
for m in range(M):
	(A, B, C) = map(int, input().split())
	adj[A][B] = min(adj[A][B], C)
	adj[B][A] = min(adj[B][A], C)
res = float('inf')
for k in range(1, N + 1):
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
for perm in itertools.permutations(r):
	best = 0
	for (x, y) in zip(perm, perm[1:]):
		best += adj[x][y]
	res = min(res, best)
print(res)


from itertools import permutations
(n, m, r) = map(int, input().split())
rl = list(map(int, input().split()))
d = [[10 ** 8] * n for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = d[b - 1][a - 1] = 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])
m = 10 ** 9
for i in permutations(rl):
	c = 0
	for j in range(1, r):
		c += d[i[j - 1] - 1][i[j] - 1]
	m = min(m, c)
print(m)


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


from itertools import permutations
(n, m, r) = map(int, input().split())
A = list(map(int, input().split()))
d = [[1e+18] * n for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = d[b - 1][a - 1] = 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])
ans = 1e+18
for x in permutations(A):
	l = 0
	for i in range(r - 1):
		l += d[x[i] - 1][x[i + 1] - 1]
	ans = min(ans, l)
print(ans)


import itertools
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
D = [[float('inf') for _ in range(N)] for _ in range(N)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	D[a][b] = c
	D[b][a] = c
for i in range(N):
	D[i][i] = 0
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])
ans = float('inf')
for p in list(itertools.permutations(r)):
	d = 0
	for i in range(R - 1):
		d += D[p[i] - 1][p[i + 1] - 1]
	ans = min(d, ans)
print(ans)


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


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


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

def warshall_floyd(n, d):
	for i in range(n):
		for j in range(n):
			for k in range(n):
				d[j][k] = min(d[j][k], d[j][i] + d[i][k])
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
d = [[1000000000] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(A, B, C) = map(int, input().split())
	d[A][B] = C
	d[B][A] = C
warshall_floyd(N + 1, d)
result = 1000000000
for p in permutations(r):
	t = 0
	for i in range(R - 1):
		t += d[p[i]][p[i + 1]]
	result = min(result, t)
print(result)


from itertools import permutations
(n, m, r) = map(int, input().split())
r_l = [int(i) - 1 for i in input().split()]
town = [[float('INF')] * n for _ in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	town[a - 1][b - 1] = c
	town[b - 1][a - 1] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			town[i][j] = min(town[i][j], town[i][k] + town[k][j])
res = float('INF')
for root in list(permutations(r_l)):
	tmp = 0
	for i in range(1, r):
		tmp += town[root[i]][root[i - 1]]
	res = min(tmp, res)
print(res)


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 floyd_warshall
from itertools import permutations

def main():
	(N, M, R) = map(int, input().split())
	d = [[float('inf')] * N for i in range(N)]
	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()


import itertools
(N, M, R) = map(int, input().split())
r = [int(x) - 1 for x in input().split()]
G = [[10 ** 7 for j in range(N)] for i in range(N)]
for i in range(N):
	G[i][i] = 0
for i in range(M):
	(a, b, c) = map(int, input().split())
	G[a - 1][b - 1] = c
	G[b - 1][a - 1] = c

def warshall_floyd(G):
	for k in range(N):
		for i in range(N):
			for j in range(N):
				G[i][j] = min(G[i][k] + G[k][j], G[i][j])
	return G
G = warshall_floyd(G)
D = 10 ** 8
for L in itertools.permutations(r):
	d = 0
	pre = L[0]
	for l in L[1:]:
		d += G[pre][l]
		pre = l
	D = min(d, D)
print(D)


INF = 10 ** 10
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
dp = [[INF] * (N + 1) for i in range(N + 1)]
for i in range(N + 1):
	dp[i][i] = 0
for i in range(M):
	(a, b, c) = map(int, input().split())
	dp[a][b] = c
	dp[b][a] = c
for k in range(1, N + 1):
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
ans = INF
import itertools
for it in itertools.permutations(r):
	tmpans = 0
	for i in range(1, R):
		tmpans += dp[it[i - 1]][it[i]]
	ans = min(ans, tmpans)
print(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)))


(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
for k in range(n):
	for i in range(n):
		for j in range(n):
			s[i][j] = min(s[i][j], s[i][k] + s[k][j])
ans = float('inf')
from itertools import permutations
for i in permutations(t):
	an = 0
	for j in range(r - 1):
		an += s[i[j] - 1][i[j + 1] - 1]
	ans = min(ans, an)
print(ans)


import itertools
INF = 10 ** 10
(N, M, R) = map(int, input().split())
(*r,) = map(int, input().split())
r = [v - 1 for v in r]
g = [[INF] * N for _ in range(N)]
for i in range(N):
	g[i][i] = 0
for m in range(M):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	g[a][b] = c
	g[b][a] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = INF
for rs in itertools.permutations(r):
	cost = 0
	for i in range(len(rs) - 1):
		cost += g[rs[i]][rs[i + 1]]
	if cost < ans:
		ans = cost
print(ans)


import itertools
(n, m, r) = map(int, input().split())
D = [[10 ** 10] * n for _ in range(n)]
for i in range(n):
	D[i][i] = 0
R = list(map(int, input().split()))
for i in range(m):
	(a, b, c) = map(int, input().split())
	D[a - 1][b - 1] = c
	D[b - 1][a - 1] = 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])
A = []
for v in itertools.permutations(R, r):
	ans = 0
	for i in range(r - 1):
		ans += D[v[i] - 1][v[i + 1] - 1]
	A.append(ans)
print(min(A))


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


(n, m, R) = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('INF')] * n for i in range(n)]
for i in range(n):
	d[i][i] = 0
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = 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])
from itertools import permutations
per = list(permutations(r, R))
ans = float('INF')
for l in per:
	cnt = 0
	for j in range(R - 1):
		cnt += d[l[j] - 1][l[j + 1] - 1]
	ans = min(cnt, ans)
print(ans)


from itertools import permutations
(n, m, r) = map(int, input().split())
visit = list(map(int, input().split()))
dist = [[10 ** 9] * n for i 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, c)
for i in range(n):
	dist[i - 1][i - 1] = 0
for i in range(n):
	for j in range(n):
		for k in range(n):
			dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])
ans = 10 ** 9
check = permutations(visit)
for i in check:
	c = 0
	for j in range(1, r):
		c += dist[i[j - 1] - 1][i[j] - 1]
	if c < ans:
		ans = c
print(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 itertools import product, permutations
(n, m, R) = map(int, input().split())
r = list(map(int, input().split()))
INF = 10 ** 10
d = [[INF for i in range(n)] for j in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
for (k, i, j) in product(range(n), range(n), range(n)):
	d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = INF
for v in permutations(r, R):
	dis = 0
	for i in range(R - 1):
		dis += d[v[i] - 1][v[i + 1] - 1]
	ans = min(ans, dis)
print(ans)


import itertools
(N, M, R) = map(int, input().split())
rs = list(map(int, input().split()))
INF = float('inf')
es = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
	es[i][i] = 0
for _ in range(M):
	(a, b, c) = map(int, input().split())
	es[a - 1][b - 1] = c
	es[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			es[i][j] = min(es[i][j], es[i][k] + es[k][j])
ans = INF
for route in itertools.permutations(rs):
	tmp = 0
	for (a, b) in zip(route, route[1:]):
		tmp += es[a - 1][b - 1]
	ans = min(ans, tmp)
print(ans)


from itertools import permutations
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
inf = 10 ** 9
d = [[inf] * N for i in range(N)]
for i in range(M):
	(A, B, C) = map(int, input().split())
	d[A - 1][B - 1] = C
	d[B - 1][A - 1] = 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])
ans = inf
for l in permutations(r):
	start = 0
	for j in range(R - 1):
		start += d[l[j] - 1][l[j + 1] - 1]
	ans = min(start, ans)
print(ans)


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
	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):
		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()


from itertools import permutations
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
for i in range(R):
	r[i] -= 1
d = [[10000000000] * N for _ in range(N)]
for i in range(N):
	d[i][i] = 0
for i in range(M):
	(A, B, C) = map(int, input().split())
	d[A - 1][B - 1] = C
	d[B - 1][A - 1] = 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])
perms = permutations(r, R)
ans = 10000000000
for perm in perms:
	now = 0
	for i in range(R - 1):
		now += d[perm[i]][perm[i + 1]]
	ans = min(ans, now)
print(ans)


(n, m, r) = map(int, input().split())
must = list(map(lambda x: int(x) - 1, input().split()))
inf = 10 ** 18
wf = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
	wf[i][i] = 0
for _ in range(m):
	(a, b, l) = map(int, input().split())
	a -= 1
	b -= 1
	wf[a][b] = l
	wf[b][a] = l
for k in range(n):
	for i in range(n):
		for j in range(n):
			wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
can = []
import itertools
for perm in itertools.permutations(range(r)):
	ans = 0
	for i in range(r - 1):
		ans += wf[must[perm[i]]][must[perm[i + 1]]]
	can.append(ans)
print(min(can))


import itertools
(N, M, R) = map(int, input().split())
r = map(int, input().split())
l = [[1000000000.0 for i in range(N + 1)] for i in range(N + 1)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	l[a][b] = l[b][a] = c
for k in range(1, N + 1):
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			t = l[i][k] + l[k][j]
			if l[i][j] > t:
				l[i][j] = t
ans = 1000000000.0
for a in itertools.permutations(r):
	s = 0
	for (i, j) in zip(a[:-1], a[1:]):
		s += l[i][j]
	if ans > s:
		ans = s
print(ans)


import itertools
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
r = list(map(lambda x: x - 1, r))
d = [[10 ** 10] * N for _ in range(N)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
for i in range(N):
	d[i][i] = 0
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])
ans = 10 ** 10
for i in itertools.permutations(r):
	dist = 0
	for j in range(R - 1):
		dist += d[i[j]][i[j + 1]]
	ans = min(ans, dist)
print(ans)


def main():
	import sys
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 7)
	from collections import Counter, deque
	from itertools import combinations, permutations, accumulate, groupby
	from bisect import bisect_left, bisect_right
	from heapq import heapify, heappop, heappush
	from math import floor, ceil
	inf = 10 ** 17
	(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):
		d = [inf] * N
		used = [False] * N
		d[start] = 0
		used[start] = True
		edgelist = []
		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)]
	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()


import itertools
inf = 10 ** 12
(n, m, r) = map(int, input().split())
n += 1
rl = [int(i) for i in input().split()]
d = [[inf for _ in [0] * n] for _ in [0] * n]
for _ in [0] * m:
	(f, t, c) = map(int, input().split())
	d[f][t] = c
	d[t][f] = c
for i in range(n):
	for j in range(n):
		for k in range(n):
			d[j][k] = min(d[j][k], d[j][i] + d[i][k])
ans = inf
for arr in itertools.permutations(rl):
	t = 0
	for i in range(0, r - 1):
		t += d[arr[i]][arr[i + 1]]
	ans = min(ans, t)
print(ans)


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


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 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):
	(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 itertools
INF = 10 ** 30
(N, M, R) = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
dist = [[INF] * N for i in range(N)]
for i in range(M):
	(A, B, C) = map(int, input().split())
	(A, B) = (A - 1, B - 1)
	dist[A][B] = C
	dist[B][A] = C
for k in range(N):
	for i in range(N):
		for j in range(N):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = INF
for x in itertools.permutations(r):
	res = 0
	for i in range(len(x) - 1):
		res += dist[x[i]][x[i + 1]]
	ans = min(ans, res)
print(ans)


from itertools import permutations
INF = 10 ** 8
(N, M, R) = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
MAP = [[INF for i in range(N)] for j in range(N)]
for i in range(M):
	(A, B, C) = map(int, input().split())
	MAP[A - 1][B - 1] = C
	MAP[B - 1][A - 1] = C
for k in range(N):
	for i in range(N):
		for j in range(N):
			MAP[i][j] = min(MAP[i][j], MAP[i][k] + MAP[k][j])
ans = INF
for L in permutations(r):
	temp = 0
	for i in range(R - 1):
		temp += MAP[L[i]][L[i + 1]]
	ans = min(ans, temp)
print(ans)


from itertools import *
(n, m, R) = map(int, input().split())
r = map(int, input().split())
d = [[10 ** 18] * n for _ in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
for i in range(n):
	d[i][i] = 0
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])
m = 10 ** 18
for e in permutations(r):
	t = 0
	for (i, j) in zip(e, e[1:]):
		t += d[i - 1][j - 1]
	m = min(m, t)
print(m)


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)


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


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
(N, M, R) = map(int, input().split())
r = [int(i) - 1 for i in input().split()]
inf = float('inf')
mat = [[inf] * N for _ in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	if mat[a - 1][b - 1] > c:
		mat[a - 1][b - 1] = mat[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])
ans = inf
for p in list(permutations(r)):
	dist = 0
	for i in range(1, len(p)):
		dist += mat[p[i]][p[i - 1]]
	ans = min(ans, dist)
print(ans)


import itertools
(n, m, R) = map(int, input().split())
r = list(map(int, input().split()))
abc = [list(map(int, input().split())) for i in range(m)]
inf = float('inf')
data = [[inf] * (n + 1) for i in range(n + 1)]
for i in range(n + 1):
	data[i][i] = 0
for u in abc:
	(a, b, c) = u
	data[a][b] = c
	data[b][a] = c
for k in range(1, n + 1):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			data[i][j] = min(data[i][j], data[i][k] + data[k][j])
ans = inf
for h in itertools.permutations(r):
	l = 0
	for j in range(1, R):
		l += data[h[j - 1]][h[j]]
	ans = min(ans, l)
print(ans)


import itertools
(N, M, R) = map(int, input().split())
rlist = [int(r) for r in input().split()]
INF = 10 ** 9
E = [[INF] * N for _ in range(N)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	E[a - 1][b - 1] = c
	E[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			E[i][j] = min(E[i][j], E[i][k] + E[k][j])
ans = 10 ** 9
for i in range(R):
	rlist[i] -= 1
for p in itertools.permutations(rlist):
	d = 0
	for i in range(1, R):
		d += E[p[i - 1]][p[i]]
	ans = min(ans, d)
print(ans)


(n, m, R) = list(map(int, input().split()))
dist = [[float('INF') if i != j else 0 for i in range(n)] for j in range(n)]
r = list(map(int, input().split()))
for i in range(m):
	(a, b, c) = list(map(int, input().split()))
	(a, b) = (a - 1, b - 1)
	dist[a][b] = c
	dist[b][a] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
from itertools import permutations
ans = float('INF')
for e in permutations(r):
	cur = 0
	for i in range(R - 1):
		cur += dist[e[i] - 1][e[i + 1] - 1]
	ans = min(ans, cur)
print(ans)


import itertools
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
INF = float('inf')
d = [[INF for i in range(N)] for i in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
for i in range(N):
	d[i][i] = 0
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])
ans = INF
for l in list(itertools.permutations(r)):
	tmp = 0
	for i in range(R - 1):
		tmp += d[l[i] - 1][l[i + 1] - 1]
	ans = min(tmp, ans)
print(ans)


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 = []
for start in r:
	root = [10 ** 9] * N
	q = [[0, start - 1]]
	heapq.heapify(q)
	while q:
		temp = heapq.heappop(q)
		if root[temp[1]] == 10 ** 9:
			bfs(temp[0], temp[1])
	made.append(root)
ans = 10 ** 9
for order in itertools.permutations([i for i in range(len(r))]):
	temp = 0
	for i in range(len(order) - 1):
		fro = r[order[i]]
		aft = r[order[i + 1]]
		temp += abs(made[order[i]][aft - 1] - made[order[i]][fro - 1])
	ans = min(ans, temp)
print(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)
	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(int(ans))

def __starting_point():
	abc073_d()
__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
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())


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


(n, m, r) = map(int, input().split())
v = list(map(int, input().split()))
inf = 10 ** 18
d = [[inf for _ in range(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())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = 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])
import itertools
ans = 10 ** 18
for a in itertools.permutations(v):
	dis = 0
	for i in range(r - 1):
		dis += d[a[i + 1] - 1][a[i] - 1]
	ans = min(ans, dis)
print(ans)


from itertools import permutations
(N, M, R) = map(int, input().split())
(*r,) = map(int, input().split())
inf = float('inf')
d = [[inf] * N for _ in range(N)]
for _ in range(M):
	(A, B, C) = map(int, input().split())
	d[A - 1][B - 1] = C
	d[B - 1][A - 1] = 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])
ans = inf
for i in permutations(r):
	v = 0
	for j in range(R - 1):
		v += d[i[j] - 1][i[j + 1] - 1]
	ans = min(ans, v)
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))


from itertools import permutations
(N, M, R) = map(int, input().split())
r = [int(i) for i in input().split()]
inf = 10 ** 10
dp = [[[inf] * N for i in range(N)] for i in range(N + 1)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	dp[0][a - 1][b - 1] = c
	dp[0][b - 1][a - 1] = c
for k in range(1, N + 1):
	for j in range(N):
		for i in range(N):
			dp[k][j][i] = min(dp[k - 1][j][i], dp[k - 1][j][k - 1] + dp[k - 1][k - 1][i])
ans = inf
for elem in permutations(r, R):
	dis = 0
	for i in range(R - 1):
		dis += dp[N][elem[i + 1] - 1][elem[i] - 1]
	ans = min(ans, dis)
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]
		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
			self.w_e[b_i][a_i] = w_i
			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
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
	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))


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


(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
INF = 10 ** 18
d = [[INF for i in range(N)] for j in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
for i in range(N):
	d[i][i] = 0
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])
import itertools
ans = INF
for v in itertools.permutations(r, R):
	anss = 0
	for i in range(R - 1):
		anss += d[v[i] - 1][v[i + 1] - 1]
	ans = min(ans, anss)
print(ans)


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


(N, M, R) = map(int, input().split())
rs = list(map(int, input().split()))
rs = [r - 1 for r in rs]
D = [[100000 * 2000] * N for i in range(N)]
for i in range(N):
	D[i][i] = 0
for i in range(M):
	(A, B, C) = map(int, input().split())
	(A, B) = (A - 1, B - 1)
	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])
r = 100000 * 2000
import itertools
for rs2 in itertools.permutations(rs):
	r2 = 0
	for i in range(1, R):
		r2 += D[rs2[i - 1]][rs2[i]]
	r = min(r, r2)
print(r)


(n, m, r) = map(int, input().split())
root = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in [0] * m]
inf = 10 ** 10
dist = [[inf for _ in [0] * n] for _ in [0] * n]
for i in range(n):
	dist[i][i] = 0
for (a, b, c) in abc:
	dist[a - 1][b - 1] = c
	dist[b - 1][a - 1] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
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 += dist[i[j] - 1][i[j + 1] - 1]
	D = min(D, d)
print(D)


(n, m, R) = map(int, input().split())
r = [int(i) for i in input().split()]
inputs = []
d = [[10 ** 100 for i in range(n + 1)] for i in range(n + 1)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a][b] = c
	d[b][a] = c

def warshall_floyd(d):
	for k in range(n + 1):
		for i in range(n + 1):
			for j in range(n + 1):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
d = warshall_floyd(d)
ans = 10 ** 100
import itertools
for x in itertools.permutations(r):
	p = 0
	for i in range(1, R):
		p += d[x[i - 1]][x[i]]
	ans = min(ans, p)
print(ans)


from itertools import permutations, product

def inpl():
	return tuple(map(int, input().split()))
(N, M, R) = inpl()
inf = float('inf')
G = [[inf for _ in range(N + 1)] for _ in range(N + 1)]
D = inpl()
for _ in range(M):
	(a, b, c) = inpl()
	G[a][b] = c
	G[b][a] = c
for n in range(N + 1):
	G[n][n] = 0
for (i, j, k) in product(range(1, N + 1), repeat=3):
	G[j][k] = min(G[j][k], G[j][i] + G[i][k])
res = inf
for C in permutations(D, len(D)):
	res = min(res, sum([G[C[i]][C[i + 1]] for i in range(len(D) - 1)]))
print(res)


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


from itertools import permutations

def wf(d):
	n = len(d[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]
	return d
(n, m, r) = map(int, input().split())
R = min(r, 8)
d = [[10 ** 12 for i in range(n)] for j in range(n)]
l = [int(i) - 1 for i in input().split()]
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = d[b - 1][a - 1] = c
d = wf(d)
ans = 30 ** 8
for v in permutations(l):
	cnt = sum((d[v][u] for (v, u) in zip(v, v[1:])))
	ans = min(ans, cnt)
print(ans)


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


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):
		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()


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

def warshall_floyd(d):
	n = len(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
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 = 10000000000.0
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 sys
read = sys.stdin.readline

def read_ints():
	return list(map(int, read().split()))
from itertools import product, permutations, combinations
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
(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
D = dijkstra(csr_matrix(adj_mat, dtype='int'), directed=False)
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))


from itertools import product, permutations
INF = 1145141919810
(N, M, R) = map(int, input().split())
r = map(int, input().split())
road = [[0 if x == y else INF for y in range(N + 1)] for x in range(N + 1)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	road[a][b] = road[b][a] = c
for (k, i, j) in product(range(N + 1), repeat=3):
	road[i][j] = min(road[i][j], road[i][k] + road[k][j])
print(min((sum((road[p[i - 1]][p[i]] for i in range(1, R))) for p in permutations(r))))


from itertools import *
(n, m, r) = map(int, input().split())
rc = list(map(int, input().split()))
INF = 10 ** 18
d = [[INF] * n for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = 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])
ans = INF
for i in permutations(rc):
	a = 0
	i = list(i)
	for j in range(r - 1):
		a += d[i[j] - 1][i[j + 1] - 1]
	ans = min(a, ans)
print(ans)


(n, m, z) = map(int, input().split())
r = list(map(int, input().split()))
wf = [[10 ** 10 for i in range(n)] for j in range(n)]
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 i in range(n):
	wf[i][i] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
from itertools import *
ans = 10 ** 10
for vils in list(permutations(r)):
	cnt = 0
	for i in range(z - 1):
		cnt += wf[vils[i] - 1][vils[i + 1] - 1]
	if ans > cnt:
		ans = cnt
print(ans)


(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('inf')] * N for _ in range(N)]
for i in range(M):
	(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):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
from itertools import groupby, accumulate, product, permutations, combinations
ans = float('inf')
for p in permutations(r, R):
	cnt = 0
	for i in range(1, R):
		cnt += d[p[i - 1] - 1][p[i] - 1]
	ans = min(ans, cnt)
print(ans)


from itertools import permutations

def WarshallFloyd(M):
	N = len(M)
	for k in range(N):
		for j in range(N):
			for i in range(N):
				M[i][j] = min(M[i][j], M[i][k] + M[k][j])
	return M
INF = 10000000000.0
(N, M, K) = map(int, input().split())
R = [int(i) - 1 for i in input().split()]
E = [[INF] * N for _ in range(N)]
for (a, b, c) in (map(int, input().split()) for _ in range(M)):
	a -= 1
	b -= 1
	E[a][b] = E[b][a] = c
E = WarshallFloyd(E)
ans = min((sum((E[p[i]][p[i + 1]] for i in range(K - 1))) for p in permutations(R)))
print(ans)


import itertools
(N, M, R) = map(int, input().split())
rs = list(map(lambda x: int(x) - 1, input().split()))
cost = [[10 ** 9] * N for i in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	cost[a - 1][b - 1] = c
	cost[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(i):
			cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
			cost[j][i] = cost[i][j]
ans = 10 ** 9
for roads in itertools.permutations(rs):
	co = 0
	p = roads[0]
	for r in roads[1:]:
		co += cost[p][r]
		p = r
	ans = min(ans, co)
print(ans)


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))
	M = int(next(tokens))
	R = int(next(tokens))
	r = [int(next(tokens)) for _ in range(R)]
	A = [int()] * M
	B = [int()] * M
	C = [int()] * M
	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()


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


def Warshall_Floyd(edges, N):
	for k in range(N):
		for i in range(N):
			for j in range(N):
				edges[i][j] = min(edges[i][j], edges[i][k] + edges[k][j])
	return edges
import itertools
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
A = [[float('inf') for i in range(N)] for j in range(N)]
for m in range(M):
	(a, b, c) = map(int, input().split())
	A[a - 1][b - 1] = c
	A[b - 1][a - 1] = c
A = Warshall_Floyd(A, N)
ans = float('inf')
for road in list(itertools.permutations(r)):
	length = 0
	for i in range(R - 1):
		length += A[road[i] - 1][road[i + 1] - 1]
	ans = min(ans, length)
print(ans)


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 itertools
(n, m, r) = map(int, input().split())
R = min(r, 8)
d = [[10 ** 12 for i in range(n)] for j in range(n)]
l = list(map(int, input().split()))
for i in range(r):
	l[i] -= 1
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = d[b - 1][a - 1] = 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])
ans = 10 ** 12
for v in itertools.permutations(l, R):
	cnt = 0
	for i in range(1, R):
		cnt += d[v[i - 1]][v[i]]
	ans = min(ans, cnt)
print(ans)


from itertools import permutations
(N, M, R) = [int(n) for n in input().split()]
r = [int(n) - 1 for n in input().split()]
d = [[100000000] * N for n in range(N)]
for i in range(N):
	d[i][i] = 0
for m in range(M):
	(A, B, C) = [int(n) for n in input().split()]
	A -= 1
	B -= 1
	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][k] + d[k][j], d[i][j])
res = 1000000000
for perm in permutations(range(R)):
	s = 0
	for i in range(R - 1):
		s += d[r[perm[i]]][r[perm[i + 1]]]
	res = min(s, res)
print(res)


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)


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


import itertools
(N, M, R) = map(int, input().split())
towns = [int(i) for i in input().split()]
path = [[10 ** 20] * N for i in range(N)]
for i in range(N):
	path[i][i] = 0
for i in range(M):
	(a, b, c) = map(int, input().split())
	path[a - 1][b - 1] = c
	path[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(i):
			path[i][j] = min(path[i][j], path[i][k] + path[k][j])
			path[j][i] = path[i][j]
Roots = list(itertools.permutations(towns))
ans = 10 ** 20
s = 0
for r in Roots:
	for n in range(R - 1):
		s += path[r[n] - 1][r[n + 1] - 1]
	ans = min(ans, s)
	s = 0
print(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))


from itertools import permutations
(N, M, R) = map(int, input().split())
Rlist = list(map(int, input().split()))
Dmat = [[1000000000.0] * N for i in range(N)]
for i in range(N):
	Dmat[i][i] = 0
for i in range(M):
	(f, t, c) = map(int, input().split())
	Dmat[f - 1][t - 1] = c
	Dmat[t - 1][f - 1] = c
for i in range(N):
	for j in range(N):
		for k in range(N):
			Dmat[j][k] = min(Dmat[j][k], Dmat[j][i] + Dmat[i][k])
ans = 1000000000.0
for p in permutations(Rlist):
	ans = min(ans, sum([Dmat[p[i] - 1][p[i + 1] - 1] for i in range(R - 1)]))
print(ans)


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


import sys, itertools
input = sys.stdin.readline
INF = float('inf')
(n, m, r) = map(int, input().split())
R = list(map(int, input().split()))
distance = [[INF] * n for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	distance[a - 1][b - 1] = c
	distance[b - 1][a - 1] = c
for i in range(n):
	for j in range(n):
		for k in range(n):
			distance[j][k] = min(distance[j][k], distance[j][i] + distance[i][k])
ans = INF
for p in itertools.permutations(R):
	cnt = 0
	for q in range(r - 1):
		cnt += distance[p[q] - 1][p[q + 1] - 1]
	ans = min(ans, cnt)
print(ans)


import itertools
(N, M, r) = map(int, input().split())
R = [int(a) - 1 for a in input().split()]
X = [[0 if i == j else 1 << 100 for j in range(N)] for i in range(N)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	X[a - 1][b - 1] = c
	X[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			X[i][j] = min(X[i][j], X[i][k] + X[k][j])
mi = 1 << 100
for A in itertools.permutations(R, r):
	mi = min(mi, sum([X[A[i - 1]][A[i]] for i in range(1, r)]))
print(mi)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, bisect
from operator import itemgetter
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
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()
(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))


(N, M, R) = map(int, input().split())
(*r,) = map(lambda x: int(x) - 1, input().split())
D = [[float('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())
	D[a - 1][b - 1] = c
	D[b - 1][a - 1] = 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])
import itertools
ans = float('inf')
for s in itertools.permutations(r, R):
	tot = [D[s[i]][s[i + 1]] for i in range(R - 1)]
	tot = sum(tot)
	ans = min(ans, tot)
print(ans)


from itertools import permutations
(N, M, R) = map(int, input().split())
r = [int(x) for x in input().split()]
INF = float('inf')
d = [[INF for x in range(N)] for y in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
for i in range(N):
	for j in range(N):
		for k in range(N):
			if d[j][i] + d[i][k] < d[j][k]:
				d[j][k] = d[j][i] + d[i][k]
ans = INF
for root in permutations(r):
	cnt = 0
	for i in range(R - 1):
		cnt += d[root[i] - 1][root[i + 1] - 1]
		if cnt > ans:
			break
	ans = min(ans, cnt)
print(ans)


from itertools import permutations
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
G = [[10 ** 18] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	G[a][b] = c
	G[b][a] = c
for k in range(1, N + 1):
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			if G[i][k] + G[k][j] < G[i][j]:
				G[i][j] = G[i][k] + G[k][j]
ans = 10 ** 18
for elem in permutations(r):
	res = 0
	for i in range(R - 1):
		res += G[elem[i]][elem[i + 1]]
	ans = min(ans, res)
print(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 itertools import permutations
inf = float('inf')
(N, M, R) = map(int, input().split())
r = [int(s) - 1 for s in input().split()]
d = [[inf] * N for _ in range(N)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j])
ans = min([sum([d[r[p[i]]][r[p[i + 1]]] for i in range(R - 1)]) for p in permutations(range(R))])
print(ans)


from itertools import permutations as p
(N, M, R) = map(int, input().split())
r = map(int, input().split())
inf = float('inf')
l = [[inf if i != j else 0 for i in range(N)] for j in range(N)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	l[a - 1][b - 1] = c
	l[b - 1][a - 1] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			l[i][j] = min(l[i][j], l[i][k] + l[k][j])
ans = inf
for i in p(r):
	v = 0
	for j in range(R - 1):
		v += l[i[j] - 1][i[j + 1] - 1]
	ans = min(ans, v)
print(ans)


from itertools import permutations
(N, M, R) = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
INF = 10 ** 9
cost = [[INF] * N for _ in range(N)]
for _ in range(M):
	(A, B, C) = map(int, input().split())
	A -= 1
	B -= 1
	cost[A][B] = C
	cost[B][A] = C
for k in range(N):
	for i in range(N):
		for j in range(N):
			cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
ans = INF
for route in permutations(r):
	temp = 0
	for i in range(R - 1):
		temp += cost[route[i]][route[i + 1]]
	ans = min(ans, temp)
print(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)


from itertools import permutations as per
(n, m, r) = map(int, input().split())
v = list(map(int, input().split()))
for i in range(r):
	v[i] -= 1
INF = float('inf')
g = [[INF] * n for _ in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	g[a][b] = c
	g[b][a] = 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):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = INF
for l in per(range(r)):
	t = 0
	for i in range(r - 1):
		t += g[v[l[i]]][v[l[i + 1]]]
	ans = min(ans, t)
print(ans)


from scipy.sparse.csgraph import floyd_warshall
import itertools

def warshal_floyd(d):
	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])
	return d
(N, M, R) = list(map(int, input().split()))
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)
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))


(N, M, R) = map(int, input().split())
R = list(map(int, input().split()))
ABC = [tuple(map(int, input().split())) for i in range(M)]
INF = float('inf')
d = [[INF] * N for _ in range(N)]
for i in range(N):
	d[i][i] = 0
for (a, b, c) in ABC:
	(a, b) = (a - 1, b - 1)
	d[a][b] = 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])
ans = INF
import itertools
for ptn in itertools.permutations(R):
	tmp = 0
	for (a, b) in zip(ptn, ptn[1:]):
		tmp += d[a - 1][b - 1]
	ans = min(ans, tmp)
print(ans)


from itertools import permutations
(n, m, r) = map(int, input().split())
goals = list(map(int, input().split()))
goals = [g - 1 for g in goals]
g = [[pow(10, 16)] * n for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	g[a][b] = c
	g[b][a] = c
for i in range(n):
	for s in range(n):
		for t in range(n):
			g[s][t] = min(g[s][t], g[s][i] + g[i][t])
ans = float('inf')
for p in permutations(goals):
	cost = 0
	for (s, t) in zip(p[:-1], p[1:]):
		cost += g[s][t]
	ans = min(ans, cost)
print(ans)


(N, M, r) = map(int, input().split())
R = list(map(lambda x: int(x) - 1, input().split()))
d = [[1 << 30] * N for _ in range(N)]
for i in range(M):
	(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):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
from itertools import groupby, accumulate, product, permutations, combinations
ans = 1 << 30
for per in permutations(R, r):
	cnt = 0
	for i in range(r - 1):
		cnt += d[per[i]][per[i + 1]]
	ans = min(ans, cnt)
print(ans)


import itertools
(N, M, R) = map(int, input().split())
r = [int(x) - 1 for x in input().split()]
dist = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	dist[a][b] = dist[b][a] = c
for k in range(N):
	for i in range(N):
		for j in range(N):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = float('inf')
k = list(itertools.permutations(r))
for i in k:
	sumDist = 0
	for j in range(len(i) - 1):
		sumDist += dist[i[j]][i[j + 1]]
	ans = min(ans, sumDist)
print(ans)


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
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 itertools
(n, m, r) = map(int, input().split())
point = list(map(int, input().split()))
g = [[10 ** 9] * n for i in range(n)]
for _ in range(m):
	(u, v, c) = map(int, input().split())
	g[u - 1][v - 1] = g[v - 1][u - 1] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
for i in range(n):
	g[i][i] = 0
ans = 10 ** 18
for v in itertools.permutations(point):
	tmp = 0
	for i in range(r - 1):
		tmp += g[v[i] - 1][v[i + 1] - 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
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
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))


import itertools
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
for i in range(R):
	r[i] -= 1
inf = 10 ** 12
dp = [[inf] * N for i in range(N)]
for i in range(M):
	(A, B, C) = 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):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
l = list(range(R))
m = inf
for x in itertools.permutations(l, R):
	count = 0
	for i in range(len(l) - 1):
		count += dp[r[x[i]]][r[x[i + 1]]]
	m = min(count, m)
print(m)


(t, r, g) = map(int, input().split())
d = [[float('INF') for ccc in range(t)] for i in range(t)]
for i in range(t):
	d[i][i] = 0
gl = list(map(int, input().split()))
for j in range(r):
	(x, y, c) = map(int, input().split())
	d[x - 1][y - 1] = c
	d[y - 1][x - 1] = c
for i in range(t):
	for j in range(t):
		for k in range(t):
			d[k][j] = min(d[k][j], d[k][i] + d[i][j])
from itertools import permutations as pe
ans = float('INF')
for G in pe(gl):
	p = 0
	for qw in range(g - 1):
		p += d[G[qw] - 1][G[qw + 1] - 1]
	ans = min(ans, p)
print(ans)


import itertools
(N, M, R) = map(int, input().split())
r = list(map(int, input().split()))
p = list(itertools.permutations(r))
dp = [[float('inf')] * N for _ in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	dp[a - 1][b - 1] = c
	dp[b - 1][a - 1] = c
for i in range(N):
	dp[i][i] = 0
for k in range(N):
	for i in range(N):
		for j in range(N):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
ans = float('inf')
for v in p:
	temp = 0
	for i in range(len(v) - 1):
		temp += dp[v[i] - 1][v[i + 1] - 1]
	ans = min(ans, temp)
print(ans)


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


import itertools
(N, M, R) = map(int, input().split())
s = list(map(int, input().split()))
D = [[10 ** 9 + 7 for k in range(N)] for l in range(N)]
for k in range(N):
	D[k][k] = 0
for k in range(M):
	(A, B, C) = map(int, input().split())
	A -= 1
	B -= 1
	D[A][B] = C
	D[B][A] = C
for p in range(N):
	for q in range(N):
		for r in range(N):
			D[q][r] = min(D[q][r], D[q][p] + D[p][r])
cities = list(itertools.permutations(s))
ans = 10 ** 9 + 7
for p in cities:
	t = 0
	for k in range(R - 1):
		t += D[p[k] - 1][p[k + 1] - 1]
	ans = min(ans, t)
print(ans)


from itertools import permutations
(N, M, R, *L) = map(int, open(0).read().split())
city = L[:R]
inf = L[R:]
dist = [[10 ** 10] * N for i in range(N)]
for (x, y, c) in zip(*[iter(inf)] * 3):
	dist[x - 1][y - 1] = c
	dist[y - 1][x - 1] = c
for i in range(N):
	dist[i][i] = 0
for k in range(N):
	for i in range(N):
		for j in range(N):
			dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])
ans = 10 ** 10
for m in permutations(city):
	n = 0
	for i in range(R - 1):
		n += dist[m[i] - 1][m[i + 1] - 1]
	ans = min(ans, n)
print(ans)


import itertools
(N, M, R) = [int(i) for i in input().split()]
rr = [int(i) for i in input().split()]
d = [[1 << 60 for j in range(N)] for i in range(N)]
for i in range(M):
	(a, b, c) = [int(i) for i in input().split()]
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
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 = 1 << 60
for plan in itertools.permutations(rr):
	cnt = 0
	for i in range(R - 1):
		cnt += d[plan[i] - 1][plan[i + 1] - 1]
	ans = min(ans, cnt)
print(ans)


import itertools
(N, M, R) = map(int, input().split())
cities = list(map(int, input().split()))
INF = 10 ** 10
dp = [[INF] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(s, g, c) = map(int, input().split())
	dp[s][g] = c
	dp[g][s] = c
for i in range(N + 1):
	dp[i][i] = 0
for k in range(1, N + 1):
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
patterns = itertools.permutations(cities, R)
ans = INF
for ptn in patterns:
	dis = 0
	for i in range(R - 1):
		dis += dp[ptn[i]][ptn[i + 1]]
	ans = min(ans, dis)
print(ans)


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


def i1():
	return int(input())

def i2():
	return [int(i) for i in input().split()]
[N, M, R] = i2()
r = i2()
f = float('inf')
d = [[f for j in range(N)] for i in range(N)]
for i in range(N):
	d[i][i] = 0
for i in range(M):
	a = i2()
	d[a[0] - 1][a[1] - 1] = a[2]
	d[a[1] - 1][a[0] - 1] = a[2]
for i in range(N):
	for j in range(N):
		for k in range(N):
			d[j][k] = min(d[j][k], d[j][i] + d[i][k])
c = float('inf')
import itertools
for i in list(itertools.permutations(r)):
	ddd = 0
	for j in range(len(i) - 1):
		ddd += d[i[j] - 1][i[j + 1] - 1]
	c = min(c, ddd)
print(c)


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)


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 itertools
(n, m, R) = map(int, input().split())
r = list(map(int, input().split()))
g = [[100000 * 200 + 1] * n for i in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	g[a - 1][b - 1] = g[b - 1][a - 1] = c
for k in range(n):
	for i in range(n):
		for j in range(n):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
print(min((sum((g[s[i - 1] - 1][s[i] - 1] for i in range(1, R))) for s in itertools.permutations(r))))


(n, m, r) = map(int, input().split())
r = list(map(int, input().split()))
r = [t - 1 for t in r]
abc = [list(map(int, input().split())) for _ in range(m)]
d = [[2 ** 30 for _ in range(n)] for _ in range(n)]
for t in abc:
	d[t[0] - 1][t[1] - 1] = t[2]
	d[t[1] - 1][t[0] - 1] = t[2]
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])
from itertools import permutations
res = []
for t in permutations(r):
	ans = 0
	for i in range(1, len(r)):
		ans += d[t[i - 1]][t[i]]
	res.append(ans)
print(min(res))


from itertools import permutations as p

def wf(d):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
(n, m, r) = map(int, input().split())
d = [[10 ** 9] * n for i in range(n)]
rl = list(map(int, input().split()))
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
for i in range(n):
	d[i][i] = 0
dl = wf(d)
pl = list(p(rl, r))
x = 10 ** 9
for i in pl:
	t = 0
	for j in range(r - 1):
		t += dl[i[j] - 1][i[j + 1] - 1]
	x = min(x, t)
print(x)


(n, m, r) = map(int, input().split())
R = tuple(map(lambda x: int(x) - 1, input().split()))
INF = 10 ** 9
dp = [[INF] * n for _ in range(n)]
for _ in range(m):
	(a, b, c) = 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):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
from itertools import permutations
ans = INF
for p in permutations(R):
	dist = 0
	for i in range(r - 1):
		dist += dp[p[i]][p[i + 1]]
	ans = min(ans, dist)
print(ans)