#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; typedef vector vl; typedef pair pll; typedef vector > vpll; typedef vector vs; typedef long double ld; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; } struct UnionFind { static const int MAXN = 35; typedef char Index; //適切に書き換えること。符号付きでないといけないので注意 Index data[MAXN]; void init(int size_) { memset(data, -1, size_ * sizeof(*data)); } 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; } inline bool findSet(int x, int y) { return root(x) == root(y); } inline int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } inline int size(int x) { return -data[root(x)]; } }; int main() { int N, M, T; scanf("%d%d%d", &N, &M, &T); vector > g(N, vector(N, INF)); rep(i, N) g[i][i] = 0; rep(i, M) { int a, b, c; scanf("%d%d%d", &a, &b, &c), -- a, -- b; amin(g[a][b], c); amin(g[b][a], c); } rep(k, N) rep(i, N) rep(j, N) amin(g[i][j], g[i][k] + g[k][j]); vi required(T); vector important(N, false); rep(i, T) { int v; scanf("%d", &v), -- v; required[i] = v; important[v] = true; } if(T == 1) { puts("0"); return 0; } vi steiners; rep(i, N) if(!important[i]) steiners.push_back(i); int X = steiners.size(); int ans = INF; if(T >= 15) { vector > edges; rep(i, N) rep(j, i) edges.push_back(mp(g[i][j], mp(i, j))); sort(all(edges)); vector use(N, false); UnionFind uf; rep(usesteiners, 1 << X) { rep(i, N) use[i] = important[i]; int components = T; rep(i, X) if(usesteiners >> i & 1) { use[steiners[i]] = true; ++ components; } int totalcost = 0; uf.init(N); rep(i, edges.size()) { int x = edges[i].second.first, y = edges[i].second.second; if(use[x] && use[y] && uf.unionSet(x, y)) { totalcost += edges[i].first; -- components; } } if(components == 1) amin(ans, totalcost); } }else { vector dp((1 << T) * N, INF); rep(p, T) rep(q, N) dp[(1 << p) * N + q] = g[required[p]][q]; rep(S, 1 << T) { if(!(S & (S-1))) continue; rep(p, N) { int x = INF; for(int E = (S-1) & S; E > 0; (-- E) &= S) amin(x, dp[E * N + p] + dp[(S - E) * N + p]); dp[S * N + p] = x; } rep(p, N) { int x = INF; rep(q, N) amin(x, dp[S * N + q] + g[p][q]); dp[S * N + p] = x; } } int U = (1 << T) - 1; rep(S, 1 << T) rep(q, N) amin(ans, dp[S * N + q] + dp[(U - S) * N + q]); } printf("%d\n", ans); return 0; }