#include namespace { #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wunused-function" #include #pragma GCC diagnostic pop using namespace std; using namespace atcoder; #define rep(i,n)for (int i = 0; i < int(n); ++i) #define rrep(i,n)for (int i = int(n)-1; i >= 0; --i) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template void chmax(T& a, const T& b) { a = max(a, b); } template void chmin(T& a, const T& b) { a = min(a, b); } using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VL = vector; using VVL = vector; template std::vector dijkstra(std::vector>>& to, int s=0) { const unsigned long long INF = 1002003004005006007; struct QueElem { int v; unsigned long long c; bool operator<(const QueElem a) const {return c > a.c;} QueElem(int v, unsigned long long c): v(v), c(c) {} }; std::priority_queue q; std::vector dist(to.size(), INF); dist[s] = 0; q.emplace(s, 0); while(!q.empty()) { QueElem qe = q.top(); q.pop(); int u = qe.v; unsigned long long c = qe.c; if (c > dist[u]) continue; for(auto vc: to[u]) { int v = vc.first; unsigned long long nc = c + vc.second; if (nc < dist[v]) { dist[v] = nc; q.emplace(v, nc); } } } return dist; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m, k; cin >> n >> m >> k; vector> to1(n); VI r(k); rep(i, k) cin >> r[i], r[i]--; sort(all(r)); VI ps{0, n - 1}; vector> es(k); int nxt = 0; rep(i, m) { int a, b, c; cin >> a >> b >> c; a--, b--; ps.emplace_back(a); ps.emplace_back(b); to1[a].emplace_back(b, c); to1[b].emplace_back(a, c); if (nxt < k && i == r[nxt]) { es[nxt++] = {a, b, c}; } } sort(all(ps)); ps.erase(unique(all(ps)), ps.end()); int sz = ps.size(); vector> to2(sz << k); rep(i, sz) { auto d = dijkstra(to1, ps[i]); rep(j, sz) { int c = d[ps[j]]; rep(s, 1 << k) to2[s | i << k].emplace_back(s | j << k, c); } } rep(i, k) { auto [u, v, c] = es[i]; int ui = lower_bound(all(ps), u) - ps.begin(); int vi = lower_bound(all(ps), v) - ps.begin(); rep(s, 1 << k) { int ns = s | 1 << i; to2[s | ui << k].emplace_back(ns | vi << k, c); to2[s | vi << k].emplace_back(ns | ui << k, c); } } auto d = dijkstra(to2); cout << d.back() << '\n'; }