#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
struct A {
int v, w;
bool operator < (const A& o) const {
return w > o.w;
}
};
priority_queue<A> pq;
vector<A> adj[N];
int dis[2][N];
bool vis[N];
int travel_plan(int _N, int M, int R[][2], int L[], int K, int P[]) {
for (int i = 0;i < M;i++) {
adj[R[i][0]].push_back({ R[i][1], L[i] });
adj[R[i][1]].push_back({ R[i][0], L[i] });
}
memset(dis, 0x3f, sizeof dis);
for (int i = 0;i < K;i++) {
dis[0][P[i]] = dis[1][P[i]] = 0;
pq.push({ P[i], 0 });
}
while (!pq.empty()) {
auto x = pq.top();
pq.pop();
int v = x.v, w = x.w;
if (vis[v]) continue;
vis[v] = 1;
for (auto& x : adj[v]) {
if (w + x.w < dis[0][x.v]) {
dis[1][x.v] = dis[0][x.v];
dis[0][x.v] = w + x.w;
pq.push({ x.v, dis[1][x.v] });
}
else if (w + x.w < dis[1][x.v]) {
dis[1][x.v] = w + x.w;
pq.push({ x.v, dis[1][x.v] });
}
}
}
return dis[1][0];
}
