#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define endl '\n'
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<pll> adj[N+1];
ll dis[N+1]={}, dis2[N+1]={};
for(int i=0;i<=N;i++) dis[i]=dis2[i]=LONG_LONG_MAX;
for(int i = 0;i < M;i++)
{
int u=R[i][0], v=R[i][1];
adj[u].pb({v, L[i]});
adj[v].pb({u, L[i]});
}
priority_queue<pll> pq;
for(int i = 0;i < K;i++) {
auto u=P[i];
dis[u]=dis2[u]=0;
pq.push({0,u});
}
while(sz(pq)) {
auto[cw, x]=pq.top();
pq.pop();
cw*=-1;
if(cw!=dis2[x]||cw==LONG_LONG_MAX) continue;
for(auto[i, w] : adj[x]) {
if(cw+w<dis[i]) {
dis2[i]=min(dis[i], dis2[i]);
dis[i]=cw+w;
pq.push({-dis2[i], i});
}
else if(cw+w<dis2[i]) {
dis2[i]=cw+w;
pq.push({-dis2[i], i});
}
}
}
return dis2[0];
}
