#include // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; const ll INF=4e18; void print0(){}; template void print0(H h,T... t){cout<void print1(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print1(t...);} #define debug1(a) { cerr<<#a<<":"<>>& graph, vector& is_city) { int N = graph.size(); int K = 0; vector cityid(N, -1); for (int u = 0; u < N; u++) { if (is_city[u]) { cityid[u] = K; K++; } } ll ans = INF; { vector> dp(N, vector(1 << K, INF)); for (int u = 0; u < N; u++) { if (cityid[u] >= 0) { int city = cityid[u]; dp[u][1 << city] = 0; } dp[u][0] = 0; } for (int s = 1; s < (1 << K); s++) { for (int u = 0; u < N; u++) { for (int j = s;; j = (j - 1) & s) { int k = s ^ j; // 残り if (k > 0 && j > 0) { dp[u][s] = min(dp[u][s], dp[u][j] + dp[u][k]); } if (!j) break; } } priority_queue, vector>, greater>> pq; for (int u = 0; u < N; u++) { int city = cityid[u]; if (dp[u][s] == INF) continue; pq.push({dp[u][s], u}); } vector done(N); while (pq.size()) { ll cost; int u; tie(cost, u) = pq.top(); pq.pop(); if (done[u]) continue; done[u] = true; dp[u][s] = min(dp[u][s], cost); if (cityid[u] >= 0) { int t = (1 << cityid[u]) | s; dp[u][t] = min(dp[u][t], cost); } for (auto e : graph[u]) { pq.push({e.second + cost, e.first}); } } } for (int u = 0; u < N; u++) { ans = min(ans, dp[u][(1 << K) - 1]); } } return ans; } }; // namespace SteinerTree namespace LargeSolver { class unionfind { public: vector partition; vector rank; vector siz; int n; unionfind(int n_) { partition.resize(n_); rank.resize(n_); siz.resize(n_); for (int x = 0; x < n_; x++) { partition[x] = x; rank[x] = 0; siz[x] = 1; } n = n_; } int find(int x) { if (partition[x] == x) { return x; } else { partition[x] = find(partition[x]); return partition[x]; } } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) { return; } int sx = siz[x]; int sy = siz[y]; if (rank[x] < rank[y]) { partition[x] = y; } else { partition[y] = x; if (rank[x] == rank[y]) { rank[x]++; } } siz[find(x)] = sx + sy; } bool same(int x, int y) { return find(x) == find(y); } int clstsize(int x) { return siz[find(x)]; } vector>> get_clusters() { vector> con(n); for (int i = 0; i < n; i++) { con[find(i)].push_back(i); } vector>> result; for (int i = 0; i < n; i++) { if (con[i].size() > 0) { vector members = con[i]; result.push_back({i, members}); } } return result; } }; int solve(vector>>& graph, vector& is_city) { int N = graph.size(); vector viintages; for (int u = 0; u < N; u++) { if (!is_city[u]) viintages.push_back(u); } vector edgs; for (int u = 0; u < N; u++) { for (auto e : graph[u]) { int v = e.first; int c = e.second; if (u > v) continue; edgs.push_back(c * (1 << 20) + u * (1 << 10) + v); } } sort(edgs.begin(), edgs.end()); int ans = 1e9; int m = viintages.size(); for (int i = 0; i < (1 << m); i++) { int first_city = N; int usenum = 0; vector use(N); for (int u = 0; u < N; u++) { if (is_city[u]) { first_city = min(first_city, u); use[u] = true; usenum++; } } for (int j = 0; j < m; j++) { if ((i >> j) & 1) { use[viintages[j]] = true; usenum++; } } int now = 0; auto uf = unionfind(N); for (auto e : edgs) { int c = e >> 20; int u = (e >> 10) & 1023; int v = (e & 1023); if (!use[u] || !use[v]) continue; if (!uf.same(u, v)) { uf.unite(u, v); now += c; } } if (uf.clstsize(first_city) == usenum) { ans = min(ans, now); } } return ans; } }; // namespace LargeSolver int main() { ll N, M, T; cin >> N >> M >> T; vector>> graph(N); for (ll i = 0; i < M; i++) { ll u, v, c; cin >> u >> v >> c; u--; v--; graph[u].push_back({v, c}); graph[v].push_back({u, c}); } vector is_city(N); for (ll i = 0; i < T; i++) { ll u; cin >> u; u--; is_city[u] = true; } if (T <= 14) { print1(SteinerTree::solve(graph, is_city)); } else { print1(LargeSolver::solve(graph, is_city)); } }