#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define s second
#define f first
#define pb push_back
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
vector<vector<pair<int,int>>> al(N);
for(int i=0;i<M;i++){
al[R[i][0]].pb({R[i][1], L[i]});
al[R[i][1]].pb({R[i][0], L[i]});
}
vector<int> in(N, 0), dp(N, 1e9);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
// 2ndmin, index;
vector<pair<int,int>> mn(N, {1e9, 1e9});
for(int i=0;i<K;i++){
in[P[i]]=1e9;
dp[P[i]]=0;
mn[P[i]]={0, 0};
pq.push({0, P[i]});
}
auto upd = [&](int ind, int dist) -> bool {
pair<int,int> bef=mn[ind];
if(dist >= mn[ind].s) return 0;
if(dist <= mn[ind].f){
mn[ind].s=mn[ind].f;
mn[ind].f=dist;
}
else {
mn[ind].s=dist;
}
if(bef.s != mn[ind].s)return 1;
return 0;
};
while(!pq.empty()){
auto [smn, ind]=pq.top();pq.pop();
if(mn[ind].s < smn) continue;
for(auto [to, cost]:al[ind]){
in[to]++;
bool change = upd(to, mn[ind].s + cost);
if(in[to]>=2 and change){ // we can push this guy
pq.push({mn[to].s, to});
}
}
}
return mn[0].s;
}
