#include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; using pi = pair <int, int>; const int INF = 1e18; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("CITIES.INP", "r", stdin); freopen("CITIES.OUT", "w", stdout); int n, m, k; cin >> n >> k >> m; vector<int> imp(k); for (int i = 0; i < k; i++) cin >> imp[i]; vector<vector<pi>> adj(n+1, vector<pi>()); for (int i = 0; i < m; i++) { int u, v, c; cin >> u >> v >> c; adj[u].push_back({v, c}); adj[v].push_back({u, c}); } vector<vector<int>> DP(1<<k, vector<int>(n+1, INF)); for (int i = 0; i < k; i++) DP[1<<i][imp[i]] = 0; for (int mask = 0; mask < (1<<k); mask++) { for (int submask = mask; submask > 0; submask = ((submask - 1) & mask)) { int left = submask, right = mask ^ submask; if (left > right) continue; for (int i = 1; i <= n; i++) { DP[mask][i] = min(DP[mask][i], DP[left][i] + DP[right][i]); } } priority_queue<pi, vector<pi>, greater<pi>> pq; vector<bool> vis(n+1, false); for (int i = 1; i <= n; i++) pq.push({DP[mask][i], i}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = true; for (auto el : adj[u]) { int d = DP[mask][u] + el.second; if (d < DP[mask][el.first]) { DP[mask][el.first] = d; pq.push({d, el.first}); } } } } cout << *min_element(DP[(1<<k)-1].begin(), DP[(1<<k)-1].end()); return 0; } /* 4 3 6 1 3 4 1 2 4 1 3 9 2 3 2 2 4 5 3 4 8 1 4 6 */