#include using namespace std; using VS = vector; using LL = long long; using VI = vector; using VVI = vector; using PII = pair; using PLL = pair; using VL = vector; using VVL = vector; #define ALL(a) begin((a)),end((a)) #define RALL(a) (a).rbegin(), (a).rend() #define SZ(a) int((a).size()) #define SORT(c) sort(ALL((c))) #define RSORT(c) sort(RALL((c))) #define UNIQ(c) (c).erase(unique(ALL((c))), end((c))) #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++) #define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--) #define debug(x) cerr << #x << ": " << x << endl const int INF = 1e9; const LL LINF = 1e16; const LL MOD = 1000000007; const double PI = acos(-1.0); int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 }; int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 }; int OPT[1 << 14][40]; int minimum_steiner_tree(const vector& T, const VVI &g) {//prefield const int n = g.size(); const int numT = T.size(); if (numT <= 1) return 0; VVI d(g); // all-pair shortest /// FOR(i, 0, n)d[i][i] = 0; for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); for (int p = 0; p < numT; ++p) // trivial case for (int q = 0; q < n; ++q) OPT[1 << p][q] = d[T[p]][q]; for (int i = 1; i<1 << numT; i++)if (((i - 1) & i) != 0) { for (int j = 0; j 0; k = (k - 1) & i) { OPT[i][j] = min(OPT[i][j], OPT[k][j] + OPT[i^k][j]); } } for (int j = 0; j data; UnionFind(int n) { data.assign(n, -1); } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool same(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; struct edge { int f, t, c; edge() {} edge(int x, int y, int z) :f(x), t(y), c(z) {} bool operator < (const edge &e) const { return c < e.c; }; }; LL kruskal(const vector& es,const VI &use,const VI& Ts ,LL cur) { //sort(es.begin(), es.end()); UnionFind uf(SZ(use)); LL min_cost = 0; FOR(i, 0, SZ(es)) { if (use[es[i].f] && use[es[i].t]) if (!uf.same(es[i].f, es[i].t)) { min_cost += es[i].c; if (cur < min_cost)return INF; uf.unionSet(es[i].f, es[i].t); } } FOR(i, 0, SZ(Ts)) { if (!uf.same(Ts[0], Ts[i]))return INF; } return min_cost; } int main() { cin.tie(0); ios_base::sync_with_stdio(false); int N, M, T; cin >> N >> M >> T; VVI G(N, VI(N, INF)); FOR(i, 0, N)G[i][i] = 0; vectoredges(M); FOR(i, 0, M) { int a, b, c; cin >> a >> b >> c; a--, b--; G[a][b] = G[b][a] = c; edges[i] = edge(a, b, c); } VI t(T); FOR(i, 0, T) { cin >> t[i]; t[i]--; } LL ans; if (T < 14) { ans = minimum_steiner_tree(t, G); } else { // Tュ샑췻곖ゃ겿괒굱짒뇋?▲덯 VI now_using(N, 0); FOR(i, 0, T)now_using[t[i]] = 1; int cn = N - T; VI candidates; FOR(i, 0, N) { if (!now_using[i])candidates.push_back(i); } SORT(edges); ans = INF; FOR(state, 0, 1 << cn) { FOR(i, 0, cn) { if (state & 1 << i) { now_using[candidates[i]] = 1; } } ans = min(ans, kruskal(edges, now_using,t,ans)); FOR(i, 0, cn) { if (state & 1 << i) { now_using[candidates[i]] = 0; } } } } cout << ans << "\n"; return 0; }