#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; struct Edge { int id; int u; ll cost; Edge(int id = -1, int u = -1, ll cost = -1) { this->id = id; this->u = u; this->cost = cost; } }; vector E[210]; struct Node { int v; int mask; ll cost; Node(int v = -1, int mask = -1, ll cost = -1) { this->v = v; this->mask = mask; this->cost = cost; } bool operator>(const Node &n) const { return cost > n.cost; } }; int main() { int N, M, K; cin >> N >> M >> K; vector R(K); for (int i = 0; i < K; ++i) { cin >> R[i]; } for (int i = 1; i <= M; ++i) { int a, b; ll c; cin >> a >> b >> c; E[a].push_back(Edge(i, b, c)); E[b].push_back(Edge(i, a, c)); } priority_queue , greater> pque; pque.push(Node(1, 0, 0)); bool visited[2 << K][N + 1]; memset(visited, false, sizeof(visited)); ll ans = LLONG_MAX; while (not pque.empty()) { Node node = pque.top(); pque.pop(); if (visited[node.mask][node.v]) continue; visited[node.mask][node.v] = true; if (node.v == N && node.mask == (1 << K) - 1) { ans = min(ans, node.cost); continue; } for (Edge &e : E[node.v]) { int nmask = node.mask; for (int k = 0; k < K; ++k) { if (e.id != R[k]) continue; nmask |= (1 << k); } pque.push(Node(e.u, nmask, node.cost + e.cost)); } } cout << ans << endl; return 0; }