#include using namespace std; template struct steiner_tree{ int N; std::vector>> G; std::vector> dp; steiner_tree(int node_size) : N(node_size), G(node_size){} void add_edge(int u, int v, T cost){ assert(0 <= u && u < N); assert(0 <= v && v < N); G[u].emplace_back(v, cost); G[v].emplace_back(u, cost); } T solve(std::vector &terminal){ int t = terminal.size(); if(t == 0)return T(0); dp.resize(1 << t, std::vector(N, std::numeric_limits::max() / 2)); for(int i = 0; i < t; i++){ assert(0 <= terminal[i] && terminal[i] < N); dp[1 << i][terminal[i]] = 0; } for(int i = 1; i < (1 << t); i++){ for(int j = 0; j < N; j++){ for(int k = i; k > 0; k = (k - 1) & i){ dp[i][j] = std::min(dp[i][j], dp[k][j] + dp[i ^ k][j]); } } if(i == (1 << t) - 1) break; std::priority_queue, std::vector>, std::greater>> pq; for(int j = 0; j < N; j++){ pq.emplace(dp[i][j], j); } T d; int v; while(!pq.empty()){ std::tie(d, v) = pq.top(); pq.pop(); if(d > dp[i][v])continue; for(int j = 0, to, cost; j < G[v].size(); j++){ std::tie(to, cost) = G[v][j]; if(d + cost >= dp[i][to])continue; dp[i][to] = d + cost; pq.emplace(dp[i][to], to); } } } return dp.back()[terminal[0]]; } }; int main(){ int N, M, T; cin >> N >> M >> T; vector> edge(M); vector V(T); for(int i = 0; i < M; i++){ cin >> edge[i][1] >> edge[i][2] >> edge[i][0]; edge[i][1]--, edge[i][2]--; } for(auto &&v:V)cin >> v, v--; if(T <= 16){ steiner_tree st(N); for(auto a:edge){ st.add_edge(a[1], a[2], a[0]); } cout << st.solve(V) << endl; }else{ sort(edge.begin(), edge.end()); sort(V.begin(), V.end()); vector T; for(int i = 0; i < N; i++){ if(binary_search(V.begin(), V.end(), i))continue; T.push_back(i); } int ans = 1 << 30; for(int i = 0; i < (1 << T.size()); i++){ atcoder::dsu uf(N); vector NotUse(N); for(int j = 0; j < T.size(); j++){ if(i >> j & 1)NotUse[T[j]] = true; } int sumv = 0; for(int j = 0; j < M; j++){ if(uf.same(edge[j][1], edge[j][2]) || NotUse[edge[j][1]] || NotUse[edge[j][2]])continue; sumv += edge[j][0]; uf.merge(edge[j][1], edge[j][2]); } bool flag = true; for(int j = 1; j < V.size(); j++){ if(!uf.same(V[0], V[j])){ flag = false; break; } } if(flag)ans = min(ans, sumv); } cout << ans << '\n'; } }