#line 1 "library/Template/template.hpp" #include using namespace std; #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(v) (v).begin(),(v).end() using ll=long long int; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; templateinline bool chmax(T& a,T b){if(ainline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} #line 2 "library/Utility/fastio.hpp" #include class FastIO{ static constexpr int L=1<<16; char rdbuf[L]; int rdLeft=0,rdRight=0; inline void reload(){ int len=rdRight-rdLeft; memmove(rdbuf,rdbuf+rdLeft,len); rdLeft=0,rdRight=len; rdRight+=fread(rdbuf+len,1,L-len,stdin); } inline bool skip(){ for(;;){ while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++; if(rdLeft==rdRight){ reload(); if(rdLeft==rdRight)return false; } else break; } return true; } template::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdLeft::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft='0' and rdbuf[rdLeft]<='9' and rdLeft=rdRight)reload(); x=rdbuf[rdLeft++]; return true; } inline bool _read(string& x){ if(!skip())return false; for(;;){ int pos=rdLeft; while(pos' ')pos++; x.append(rdbuf+rdLeft,pos-rdLeft); if(rdLeft==pos)break; rdLeft=pos; if(rdLeft==rdRight)reload(); else break; } return true; } templateinline bool _read(vector& v){ for(auto& x:v){ if(!_read(x))return false; } return true; } char wtbuf[L],tmp[50]; int wtRight=0; inline void flush(){ fwrite(wtbuf,1,wtRight,stdout); wtRight=0; } inline void _write(const char& x){ if(wtRight>L-32)flush(); wtbuf[wtRight++]=x; } inline void _write(const string& x){ for(auto& c:x)_write(c); } template::value,int> =0>inline void _write(T x){ if(wtRight>L-32)flush(); if(x==0){ _write('0'); return; } else if(x<0){ _write('-'); if (__builtin_expect(x == std::numeric_limits::min(), 0)) { switch (sizeof(x)) { case 2: _write("32768"); return; case 4: _write("2147483648"); return; case 8: _write("9223372036854775808"); return; } } x=-x; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } templateinline void _write(const vector& v){ rep(i,0,v.size()){ if(i)_write(' '); _write(v[i]); } } public: FastIO(){} ~FastIO(){flush();} inline void read(){} template inline void read(Head& head,Tail&... tail){ assert(_read(head)); read(tail...); } templateinline void write(){if(ln)_write('\n');} template inline void write(const Head& head,const Tail&... tail){ if(space)_write(' '); _write(head); write(tail...); } }; /** * @brief Fast IO */ #line 3 "sol.cpp" struct SteinerTree{ using P=pair; int n; vector> g; SteinerTree(int _n):n(_n),g(n){} void add_edge(int u,int v,ll c){ g[u].push_back({v,c}); g[v].push_back({u,c}); } ll run(vector& term){ int k=term.size(); if(k<=1)return 0; vector dp(1<(n,INF)); rep(i,0,k)dp[1<; rep(mask,1,1<,greater

> pq; rep(v,0,n)pq.push({dp[mask][v],v}); while(!pq.empty()){ auto [d,v]=pq.top(); pq.pop(); if(dp[mask][v] par; int n; UnionFind(){} UnionFind(int _n):par(_n,-1),n(_n){} int root(int x){return par[x]<0?x:par[x]=root(par[x]);} bool same(int x,int y){return root(x)==root(y);} int size(int x){return -par[root(x)];} bool unite(int x,int y){ x=root(x),y=root(y); if(x==y)return false; if(size(x)>size(y))swap(x,y); par[y]+=par[x]; par[x]=y; n--; return true; } }; /** * @brief Union Find */ #line 42 "sol.cpp" FastIO io; int main(){ int n,m,t; io.read(n,m,t); if(t<=15){ SteinerTree buf(n); rep(i,0,m){ int a,b,c; io.read(a,b,c); a--; b--; buf.add_edge(a,b,c); } vector vs(t); io.read(vs); for(auto& v:vs)v--; ll ret=buf.run(vs); io.write(ret); } else{ using P=pair; using T=pair; vector es; rep(i,0,m){ int a,b,c; io.read(a,b,c); a--; b--; es.push_back({c,{a,b}}); } sort(ALL(es)); vector vs(t); io.read(vs); for(auto& v:vs)v--; int ret=inf; auto process=[&](ll mask){ int x=__builtin_popcountll(mask); UnionFind uni(n); int sub=0; for(auto& [c,uv]:es){ auto [u,v]=uv; if(mask>>u&1 and mask>>v&1){ if(uni.unite(u,v)){ x--; sub+=c; } } } if(x==1)chmin(ret,sub); }; ll used=0; rep(i,0,t)used|=1LL<