#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define sz(v) ((int)v.size())
#define all(v) (v).begin(),(v).end()
#define ll long long
int travel_plan(int n, int m, int R[][2], int len[], int ps, int P[])
{
vector<vector<int>> adj(n);
L(i,0,m-1){
auto [a,b]=R[i];
adj[a].push_back(i);
adj[b].push_back(i);
}
const ll MOD=1e9;
vector<pair<ll,ll>> dp(n,{MOD,MOD});
priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> pq;
L(i,0,ps-1){
dp[P[i]]={0,0};
pq.push({0,0,P[i]});
}
while(!pq.empty()){
auto [b,a,v]=pq.top();
pq.pop();
if(make_pair(a,b)!=dp[v])continue;
for(auto e: adj[v]){
int vai=R[e][0]^R[e][1]^v;
ll w=len[e];
if(dp[vai].second>a+w){
dp[vai].first=dp[vai].second;
dp[vai].second=a+w;
pq.push({dp[vai].second,dp[vai].first,vai});
}
else if(dp[vai].first>a+w){
dp[vai].first=a+w;
pq.push({dp[vai].second,dp[vai].first,vai});
}
}
}
/*
L(i,0,n-1){
cout<<dp[i].first<<" "<<dp[i].second<<"\n";
}
*/ return dp[0].first;
}
