#include "crocodile.h"
#include <queue>
#define N 100000
#define M 1000000
#define INF 1000000000
using namespace std;
struct Inque{
int x;
int w;
Inque(int _x=0,int _w=0):x(_x),w(_w){}
bool operator<(const Inque &r)const{
return w>r.w;
}
};
int sta[N+1],chi[M*2+1],wei[M*2+1],nxt[M*2+1],m,n;
int d[2][N+1];
bool v[N+1];
priority_queue<Inque> Q;
void addEdge(int x,int y,int w,int p){
nxt[p]=sta[x];
chi[p]=y;
wei[p]=w;
sta[x]=p;
}
int travel_plan(int _n, int _m, int R[][2], int L[], int K, int P[])
{
int i,j;
n=_n; m=_m;
for(i=0;i<m;i++){
addEdge(R[i][0],R[i][1],L[i],i*2+1);
addEdge(R[i][1],R[i][0],L[i],i*2+2);
}
for(i=0;i<n;i++){
for(j=0;j<2;j++) d[j][i]=INF+1;
}
for(i=0;i<K;i++){
for(j=0;j<2;j++) d[j][P[i]]=0;
Q.push(Inque(P[i],0));
}
for(i=0;i<n;i++){
while(!Q.empty() && v[Q.top().x]) Q.pop();
if(Q.empty()) break;
Inque t=Q.top(); Q.pop();
if(t.x==0) break;
v[t.x]=true;
for(j=sta[t.x];j;j=nxt[j]){
bool l=true;
if(d[0][chi[j]]>t.w+wei[j]){
d[1][chi[j]]=d[0][chi[j]];
d[0][chi[j]]=t.w+wei[j];
}
else if(d[1][chi[j]]>t.w+wei[j]){
d[1][chi[j]]=t.w+wei[j];
}
else{
l=false;
}
if(l){
if(d[1][chi[j]]!=INF+1){
Q.push(Inque(chi[j],d[1][chi[j]]));
}
}
}
}
return d[1][0];
}
