#include using namespace std; #include using namespace atcoder; //using mint = modint998244353; using mint = modint1000000007; using ll = long long; using ld = long double; using pll = pair; using tlll = tuple; //constexpr ll INF = 1LL << 60; template bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;} template bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;} ll safemod(ll A, ll M) {return (A % M + M) % M;} ll divfloor(ll A, ll B) {if (B < 0) {return divfloor(-A, -B);} return (A - safemod(A, B)) / B;} ll divceil(ll A, ll B) {if (B < 0) {return divceil(-A, -B);} return divfloor(A + B - 1, B);} #define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false) constexpr int INF = 1LL << 30; template class graph { public: struct edge { ll to; T cost; edge(ll to, T cost) : to(to), cost(cost) {} }; ll N; vector> G; graph(ll n) { N = n; G.resize(N); } void connect(ll sv, ll gv, T c) { G.at(sv).push_back(edge(gv, c)); } void connect2(ll v0, ll v1, T c) { connect(v0, v1, c), connect(v1, v0, c); } vector _01bfs(ll sv) { vector costs(N, INF); costs.at(sv) = 0; deque> deq; for (auto e : G.at(sv)) { if (e.cost == 0) deq.push_front(make_tuple(e.cost, sv, e.to)); else deq.push_back(make_tuple(e.cost, sv, e.to)); } while (!deq.empty()) { auto [c, pv, v] = deq.front(); deq.pop_front(); if (chmin(costs.at(v), costs.at(pv) + c)) { for (auto e : G.at(v)) { if (e.cost == 0) deq.push_front(make_tuple(e.cost, v, e.to)); else deq.push_back(make_tuple(e.cost, v, e.to)); } } } return costs; } vector dijkstra(ll sv) { vector costs(N, INF); costs.at(sv) = 0; priority_queue, vector>, greater>> pque; pque.emplace(make_pair(0, sv)); while (!pque.empty()) { auto [c, v] = pque.top(); pque.pop(); if (costs.at(v) < c) continue; for (auto e : G.at(v)) { T nc = c + e.cost; if (costs.at(e.to) > nc) { costs.at(e.to) = nc; pque.emplace(nc, e.to); } } } return costs; } }; ll ptol(ll i, ll bt, ll K) { return i * (1LL << K) + bt; } int main() { ll N, M, K; cin >> N >> M >> K; vector invR(M, -1); for (ll i = 0; i < K; i++) { ll r; cin >> r; r--; invR.at(r) = i; } graph gr(N * (1LL << K)); for (ll i = 0; i < M; i++) { ll a, b, c; cin >> a >> b >> c; a--, b--; for (ll bt = 0; bt < (1LL << K); bt++) { ll nbt = bt; if (invR.at(i) != -1) nbt |= (1LL << invR.at(i)); ll u = ptol(a, bt, K), nu = ptol(b, nbt, K); ll v = ptol(b, bt, K), nv = ptol(a, nbt, K); gr.connect(u, nu, c); gr.connect(v, nv, c); } } ll sv = ptol(0, 0, K), gv = ptol(N - 1, (1LL << K) - 1, K); auto dists = gr.dijkstra(sv); ll ans = dists.at(gv); cout << ans << endl; }