#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--)) #define all(a) a.begin(), a.end() #define ppf pop_front #define ppb pop_back #define pf push_front #define pb push_back #define fr first #define sc second #define ii pair<int, int> #define iii tuple<int, int, int> #define vc vector #define sz(a) a.size() #define mnto(x,y) x = min(x, (__typeof__(x))y) #define mxto(x,y) x = max(x, (__typeof__(x))y) #define setval(arr, x) memset(arr, x, sizeof(arr)) template<typename T> using vv = vc<vc<T>>; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 1e5+5; const int INF = 1e18; int n, m, k; vc<ii> adj[N]; vc<int> special; vc<int> dijkstra(int src, const vc<bool> &skip) { vc<int> dist(n+1, INF); vc<bool> visited(n+1, 0); priority_queue<ii, vc<ii>, greater<>> pq; dist[src] = 0; pq.push({0, src}); while (sz(pq)) { int u = pq.top().sc; pq.pop(); if (visited[u]) continue; visited[u] = 1; for (auto &[v, w] : adj[u]) { if (skip[v]) continue; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; } iii nsp(const vc<bool> &skip) { vc<int> dist(n+1, INF); vc<int> source(n+1, -1); vc<bool> visited(n+1, 0); priority_queue<ii, vc<ii>, greater<>> pq; for (int u : special) { if (skip[u]) continue; dist[u] = 0; source[u] = u; pq.push({0, u}); } while (sz(pq)) { int u = pq.top().sc; pq.pop(); if (visited[u]) continue; visited[u] = 1; for (auto &[v, w] : adj[u]) { if (skip[v]) continue; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; source[v] = source[u]; pq.push({dist[v], v}); } } } int best = INF; int a = -1, b = -1; rep(u, 1, n+1) { if (skip[u]) continue; for (auto &[v, w] : adj[u]) { if (skip[v]) continue; if (source[u] != source[v] && dist[u] != INF && dist[v] != INF) { int tot = dist[u] + w + dist[v]; if (tot < best) { best = tot; a = source[u]; b = source[v]; } } } } return {a, b, best}; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> k; rep(i, 0, m) { int u, v, w; cin >> u >> v >> w; adj[u].pb({v, w}); adj[v].pb({u, w}); } special.resize(k); vc<bool> skip(n+1, 0); rep(i, 0, k) cin >> special[i]; auto [x1, y1, d1] = nsp(skip); auto dx1 = dijkstra(x1, skip); auto dy1 = dijkstra(y1, skip); int ans = INF; int c1 = -1, c2 = -1; for (int u : special) { if (u == x1 || u == y1) continue; if (c1 == -1 || dy1[u] <= dy1[c1]) { c2 = c1; c1 = u; } else if (c2 == -1 || dy1[u] < dy1[c2]) c2 = u; } if (dx1[c1] != INF && dy1[c2] != INF) mnto(ans, dx1[c1] + dy1[c2]); for (int x2 : special) { if (x2 == x1 || x2 == y1 || x2 == c1) continue; if (dx1[x2] != INF && dy1[c1] != INF) mnto(ans, dx1[x2] + dy1[c1]); } skip[x1] = skip[y1] = 1; auto [x3, y3, d2] = nsp(skip); if (d1 != INF && d2 != INF) mnto(ans, d1+d2); cout << ans; }