#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define ll long long
#define ii pair<ll, ll>
#define ff first
#define ss second
#define fto(i, a, b, x) for (int i = a; i <= b; i += x)
const ll MAXN = 100005; // N la 10^5
const ll INF = 1e16; // Dung 1e16 de an toan khi cong w
vector<ii> dothi[MAXN];
ll dist1[MAXN], dist2[MAXN];
bool visited[MAXN];
void dijkstra(int n, int k, int p[]) {
priority_queue<ii, vector<ii>, greater<ii>> pq;
fto(i, 0, n, 1) {
dist1[i] = dist2[i] = INF;
visited[i] = false;
}
fto(i, 0, k - 1, 1) {
int u = p[i];
dist1[u] = dist2[u] = 0;
pq.push({0, u});
}
while (!pq.empty()) {
ll d = pq.top().ff;
int u = (int)pq.top().ss;
pq.pop();
if (d > dist2[u] || visited[u]) continue;
visited[u] = true;
for (auto &edge : dothi[u]) {
int v = (int)edge.ff;
ll w = d + edge.ss;
if (w < dist1[v]) {
dist2[v] = dist1[v];
dist1[v] = w;
if (dist2[v] != INF) pq.push({dist2[v], v});
} else if (w < dist2[v]) {
dist2[v] = w;
pq.push({dist2[v], v});
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
// Luon xoa du lieu cu o dau ham
fto(i, 0, N, 1) dothi[i].clear();
fto(i, 0, M - 1, 1) {
int u = R[i][0], v = R[i][1];
ll w = L[i];
dothi[u].push_back({v, w});
dothi[v].push_back({u, w});
}
dijkstra(N, K, P);
return (int)dist2[0]; // Entrance luon la 0 theo de bai
}
