//Let's join Kaede Takagaki Fan Club !! #include #include #include using namespace std; typedef long long ll; typedef pair P; typedef pair P1; typedef pair P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define fi first #define sc second #define rep(i,x) for(int i=0;i void dmp(T a){ rep(i,a.size()) cout << a[i] << " "; cout << endl; } template bool chmax(T&a, T b){ if(a < b){ a = b; return 1; } return 0; } template bool chmin(T&a, T b){ if(a > b){ a = b; return 1; } return 0; } template void g(T &a){ cin >> a; } template void o(const T &a,bool space=false){ cout << a << (space?' ':'\n'); } //ios::sync_with_stdio(false); const ll mod = 1000000007;//998244353 template void add(T&a,T b){ a+=b; if(a >= mod) a-=mod; } int n, m, t; int w[36][36]; vectoredge; vectorimp; int dp[(1<<16)][36]; void solve_steiner(){ repn(i, (1<<16)-1) rep(j, 36) dp[i][j] = INF; rep(i, imp.size()){ rep(j, n){ dp[(1<ump; bool ex[36]={}; rep(i, imp.size()) ex[imp[i]] = 1; rep(i, n) if(!ex[i]) ump.pb(i); int sz = ump.size(), ans = INF; rep(mask, (1<>i)&1)) eex[ump[i]] = 1; kaede.init(); rep(i, edge.size()){ int a = edge[i].sc.fi, b = edge[i].sc.sc; if(!ex[a] && !eex[a]) continue; if(!ex[b] && !eex[b]) continue; if(kaede.same(a, b)) continue; kaede.unite(a, b); cnt ++; use += edge[i].fi; } if(cnt == N-1) chmin(ans, use); } cout << ans << endl; } int main(){ cin >> n >> m >> t; rep(i, 36) rep(j, 36){ if(i != j) w[i][j] = 1e7; } rep(i, m){ int a, b, c; cin >> a >> b >> c; a --; b --; w[a][b] = w[b][a] = c; edge.pb(mp(c, mp(a, b))); } sort(all(edge)); imp.resize(t); rep(i, t){ cin >> imp[i]; imp[i] --; } rep(x, n) rep(i, n) rep(j, n) chmin(w[i][j], w[i][x] + w[x][j]); if(t <= 16) solve_steiner(); else solve_MST(); }