#include #include #include #include #include #include struct DisjointSet { std::vector par; DisjointSet(int N) : par(N) { Reset(); } void Reset() { std::iota(par.begin(), par.end(), 0); } int Find(int a) { if (a == par[a]) return a; par[a] = Find(par[a]); return par[a]; } bool Union(int a, int b) { a = Find(a); b = Find(b); par[a] = b; return a != b; } }; int main() { int N, M, T; std::cin >> N >> M >> T; std::vector> E(M); for (auto &[c, a, b] : E) { std::cin >> a >> b >> c; b--; a--; } std::vector V(T); for (int &v: V) { std::cin >> v; v--; } std::vector> D(N, std::vector(N, std::numeric_limits::max() / 2)); for (int i = 0; i < N; i++) D[i][i] = 0; for (auto [c, a, b] : E) D[a][b] = D[b][a] = c; for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) D[i][j] = std::min(D[i][j], D[i][k] + D[k][j]); if (T <= 3 * N / 7) { std::vector> DP(1 << T, std::vector(N, std::numeric_limits::max() / 2)); for (int i = 0; i < T; ++i) for (int j = 0; j < N; ++j) DP[1 << i][j] = D[V[i]][j]; for (int v = 1; v < (1 << T); ++v) { for (int m1 = 0; (m1 = (m1 - v) & v);) { int m2 = v - m1; if(m2 < m1) break; for (int i = 0; i < N; i++) DP[v][i] = std::min(DP[v][i], DP[m1][i] + DP[m2][i]); } for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) DP[v][i] = std::min(DP[v][i], DP[v][j] + D[j][i]); } std::cout << *std::min_element(DP.back().begin(), DP.back().end()) << std::endl; } else { std::sort(E.begin(), E.end()); std::vector target(N); for(int v: V) target[v] = true; std::vector Vc; for(int i=0; i::max(); for(int i=0; i<(1<<(N-T)); i++) { ds.Reset(); int comp = T; for(int j=0; j