import sys import math import bisect from heapq import heapify, heappop, heappush from collections import deque, defaultdict, Counter from functools import lru_cache from itertools import accumulate, combinations, permutations, product sys.setrecursionlimit(1000000) MOD = 10 ** 9 + 7 MOD99 = 998244353 input = lambda: sys.stdin.readline().strip() NI = lambda: int(input()) NMI = lambda: map(int, input().split()) NLI = lambda: list(NMI()) SI = lambda: input() SMI = lambda: input().split() SLI = lambda: list(SMI()) EI = lambda m: [NLI() for _ in range(m)] def main(): N, M, T = NMI() ABC = EI(M) ABC = [[x-1, y-1, z] for x, y, z in ABC] V = [NI() for _ in range(T)] V = [x-1 for x in V] INF = 10 ** 15 if T <= 14: # 最小シュタイナー木 # ワーシャルフロイド D = [[INF]*N for _ in range(N)] for i in range(N): D[i][i] = 0 for a, b, c in ABC: 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]) # dp[i][S]: iを端点に持ち、Vの部分集合S(T-bit)を含むシュタイナー木の重み dp = [[INF] * (1< 0: yield s s = (s-1) & S # O(3^T)の部分集合DP # トータルでO(N*3^T + N^2*2^T) for S in range(1, 1< self.par[y]: x, y = y, x self.group_num -= 1 self.par[x] += self.par[y] self.par[y] = x def MST(N, edges, target, uf, cnt): """ 要UnionFind N頂点のうち、target[i]==1の点のみの最小全域木の長さ edges = [[u, v, cost], ....] (0-index) (sort済み) """ uf.rebuild() # edges.sort(key=lambda x: x[-1]) res = 0 for a, b, c in edges: if target[a] == 0 or target[b] == 0: continue if uf.is_same(a, b): continue else: res += c cnt -= 1 uf.unite(a, b) if cnt == 1: return res return INF ABC.sort(key=lambda x: x[-1]) Vbar = [i for i in range(N) if i not in V] Vbn = len(Vbar) target = [1] * N uf = UnionFind(N) ans = INF for case in range(1<> i) & 1: target[Vbar[i]] = 1 cnt += 1 else: target[Vbar[i]] = 0 res = MST(N, ABC, target, uf, cnt) ans = min(ans, res) if ans == T-1: print(ans) return print(ans) if __name__ == "__main__": main()