#include using namespace std; using ll = long long; #define FOR_(n) for (ll _ = 0; (_) < (ll)(n); ++(_)) #define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i)) #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define eb emplace_back template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } const int INF=1e7; int n,m,t; int w[36][36]; vector> edge; vector imp; int dp[1<<14][36]; void steiner_tree(){ FOR(k,n) FOR(i,n) FOR(j,n) chmin(w[i][j],w[i][k]+w[k][j]); FOR(i,1<<14) FOR(j,36) dp[i][j]=INF; FOR(i,len(imp)) FOR(j,n){ dp[1< ump; bool ex[36]{}; FOR(i,len(imp)) ex[imp[i]]=1; FOR(i,n) if(!ex[i]) ump.eb(i); const int sz=len(ump); int ans=INF; FOR(mask,1<>i&1) eex[ump[i]]=1; uf.init(); FOR(i,len(edge)){ auto [wt,a,b]=edge[i]; if(!ex[a] && !eex[a]) continue; if(!ex[b] && !eex[b]) continue; if(uf.same(a,b)) continue; uf.unite(a,b); cnt++; use+=wt; if(ans<=use) break; } if(cnt==N-1) chmin(ans,use); } cout<>n>>m>>t; FOR(i,36) FOR(j,36) if(i!=j) w[i][j]=INF; FOR(_,m){ int a,b,c;cin>>a>>b>>c; --a,--b; edge.emplace_back(c,a,b); w[a][b]=w[b][a]=c; } imp.resize(t); for(auto&i:imp) cin>>i,--i; if(t<=14) steiner_tree(); else solve_MST(); } int main(){ ios::sync_with_stdio(0); cin.tie(0); int t=1; //cin>>t; for(;t--;) solve(); }