Untitled

#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define int long long
const int inf = 1e17;

vector<pair<int, int>> g[100005];
vector<int> sp, isp;
vector<vector<int>> e;
int n, m, k;

vector<int> cpair(int a, int b) {
	//closest pair if nodes A and B don't exist in graph
	vector<int> rch(n + 1, 0), dist(n + 1, inf);
	set<pair<int, int>> s;
	for (auto x : sp)
		if((x != a) && (x != b))
			rch[x] = x, dist[x] = 0,
			s.insert({ 0, x });

	while (!s.empty()) {
		auto f = *s.begin();
		s.erase(s.begin());
		int node = f.second, t = f.first;
		for (auto x : g[node])
			if((x.first != a) && (x.first != b))
				if (dist[x.first] > (t + x.second)) {
					if (dist[x.first] < inf)
						s.erase({ dist[x.first], x.first });
					rch[x.first] = rch[node];
					dist[x.first] = (t + x.second);
					s.insert({ dist[x.first], x.first });
				}
	}

	pair<int, int> ans = { -1, -1 };
	int d = inf;
	for (auto x : e) {
		int u = x[0], v = x[1], w = x[2];
		if (rch[u] != rch[v])
			if (d > (dist[u] + dist[v] + w))
				d = (dist[u] + dist[v] + w),
				ans = { rch[u], rch[v] };
	}
	return { d, ans.first, ans.second };
}
vector<int> ssassp(int node) {
	//single-source-all-sink-shortest-path
	set<pair<int, int>> s;
	vector<int> dist(n + 1, inf);
	dist[node] = 0, s.insert({ 0, node });
	vector<pair<int, int>> res;

	while (!s.empty()) {
		auto f = *s.begin();
		s.erase(s.begin());
		for(auto x: g[f.second])
			if (dist[x.first] > (f.first + x.second)) {
				if (dist[x.first] < inf)
					s.erase({ dist[x.first], x.first });
				dist[x.first] = (f.first + x.second);
				s.insert({ dist[x.first], x.first });
			}
	}
	return dist;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m >> k;
	for (int i = 0; i < m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({ v, w });
		g[v].push_back({ u, w });
		e.push_back({ u, v, w });
	}
	
	sp.resize(k), isp.resize(n + 1);
	for (auto& x : sp) cin >> x;
	for (auto x : sp) isp[x] = 1;

	auto res = cpair(0, 0); 
	int a = res[1], b = res[2]; 
	set<pair<int, int>> bs;
	int ans1 = res[0] + cpair(a, b)[0], ans2 = inf;
	auto p1 = ssassp(a), p2 = ssassp(b);
	for (auto x : sp) {
		if((x != a) && (x != b)) bs.insert({ p1[x], x });
		if(bs.size() > 2) bs.erase(*bs.rbegin());
	}
	auto fm = *bs.begin(), sm = *bs.rbegin(); 
	for (auto x : sp)
		if ((x != a) && (x != b)) 
			ans2 = min(ans2, ((x == fm.second)? (sm.first + p2[x]): (fm.first + p2[x])));
	cout << min(ans1, ans2);
}