// ===== ライブラリインクルード ===== #include #include #include #include using namespace std; #include using namespace atcoder; // ===== 型の省略名定義 ===== using uint = unsigned int; using ll = long long; using ull = unsigned long long; using i128 = __int128; using vc = vector; using vvc = vector>; using vi = vector; using vvi = vector>; using vll = vector; using vvll = vector>; using vd = vector; using vvd = vector>; using pii = pair; using pll = pair; using vpii = vector; using vvpii = vector>; using vpll = vector; using vvpll = vector>; using vs = vector; // ===== 略記用マクロ ===== #define rep(i, n) for (auto i = std::decay_t{0}; i < (n); ++i) #define rrep(i, n) for (auto i = (n); i-- > 0;) #define nfor(i, l, r) for (auto i = (l); i < (r); ++i) #define rnfor(i, l, r) for (auto i = (r); i-- > (l); ) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define fi first #define se second // ===== 無限大定数 ===== constexpr int INF = 1e9 + 10; constexpr ll LINF = 4e18 + 10; constexpr i128 inf128 = 1e37 + 10; // ===== 入出力 ===== template ostream& operator<<(ostream& os, const pair& p) {return os << p.first << " " << p.second;} template concept hasval = requires(t v) {{ v.val() } -> convertible_to;}; ostream& operator<<(ostream& os, hasval auto v) {return os << v.val();} template void print_vector(const vector& v, const string& sep = "\n", bool omit_last = false) { int siz = (int)v.size(); rep(i, siz) { cout << v[i]; if(!(omit_last && i == siz - 1)) cout << sep; } } void yes_no(bool ans, bool omit_break = false) {cout << (ans ? "yes" : "no") << (omit_break ? "" : "\n");} template t ninf(t ans, t inf_val) {return (ans >= inf_val ? -1 : ans);} int ninf(int ans) {return (ans >= INF ? -1 : ans);} ll ninf(ll ans) {return (ans >= LINF ? -1 : ans);} // ===== 汎用関数 ===== template bool chmax(t &a, u b){ if(a bool chmin(t &a, u b){ if(a>b){a=b; return true;} return false;} template void dedup(vector& v) {v.erase(unique(all(v)), v.end());} // ========== テンプレ終わり ========== using mint = modint998244353; using vm = vector; using vvm = vector; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, t; cin >> n >> m >> t; vvpii g(n); rep(i, m) { int a, b, c; cin >> a >> b >> c; --a; --b; g[a].push_back({b, c}); g[b].push_back({a, c}); } vi v(t); for(int& x : v) cin >> x, --x; sort(all(v)); if(t <= 16) { vvi dp(1<> pq; nfor(s, 1, 1<= dp[s][v]) continue; dp[s][v] = d + c; pq.emplace(d + c, v); } } } cout << dp[(1< e; rep(u, n) for(auto [v, c] : g[u]) e.push_back({u, v, c}); sort(all(e), [](edge a, edge b){return a.c < b.c;}); auto spanning_tree = [&](ll S) -> ll { int ans = 0; int group = popcount((ull)S); dsu uf(n); for(auto [u, v, c] : e) { if(!(S & (1LL<