#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fr first
#define sc second
#define int long long
const int maxn = 1e5+10;
const int inf = 1e18+10;
int32_t travel_plan(int32_t n, int32_t m, int32_t R[][2], int32_t L[], int32_t k, int32_t P[])
{
vector<vector<pair<int,int>>> g(n);
for(int i = 0; i < m; i++) {
g[R[i][0]].pb(mp(R[i][1],L[i]));
g[R[i][1]].pb(mp(R[i][0],L[i]));
}
vector<int> d1(n),d2(n);
for(int i = 0; i < n; i++) {
d1[i] = d2[i] = inf;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
for(int i = 0; i < k; i++) {
int v = P[i];
d1[v] = d2[v] = 0;
pq.push(mp(0,v));
}
while(pq.size()) {
int u = pq.top().sc;
int dis2 = pq.top().fr;
pq.pop();
if(dis2 != d2[u]) continue;
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(d2[v] > d2[u]+w) {
d2[v] = d2[u]+w;
if(d2[v] < d1[v]) swap(d2[v],d1[v]);
if(d2[v] != inf) pq.push(mp(d2[v],v));
}
}
}
return (int32_t) d2[0];
}
