#include "crocodile.h"
#include <iostream>
using namespace std;
bool fin[100005];
int t[25000005],c[100005],road[5000005][3],map[100005];
long long mi[100005][4];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
for(register int i=0;i<n;i++)
{
map[i]=-1;
mi[i][0]=9999999999;
mi[i][1]=9999999999;
mi[i][2]=-1;
mi[i][3]=-1;
}
for(register int i=0;i<m;i++)
{
road[i*2][0]=r[i][0];
road[i*2][1]=map[r[i][1]];
road[i*2][2]=road[i*2+1][2]=l[i];
map[r[i][1]]=i*2;
road[i*2+1][0]=r[i][1];
road[i*2+1][1]=map[r[i][0]];
map[r[i][0]]=i*2+1;
}
register int pp=0,qq=k-1;
for(register int i=0;i<k;i++)
{
t[i]=p[i];
c[p[i]]=2;
mi[p[i]][0]=0;
mi[p[i]][1]=0;
}
while(pp<=qq)
{
if(c[t[pp]]>=2&& fin[t[pp]]==0)
{
int q=map[t[pp]];
while(q!=-1)
{
if(fin[road[q][0]]==0)
{
qq++;
c[road[q][0]]++;
t[qq]=road[q][0];
}
q=road[q][1];
}
fin[t[pp]]=1;
}
pp++;
}
pp=0;
qq=k-1;
for(register int i=0;i<n;i++)fin[i]=0;
while(pp<=qq)
{
while((fin[t[pp]]==1 || mi[t[pp]][1]==9999999999) && pp<=qq)pp++;
if(pp>qq)break;
int x=t[pp];
int q=map[x];
while(q!=-1)
{
int now=road[q][0];
if(c[now]>=2)
{
qq++;
t[qq]=now;
if(mi[x][1]+road[q][2]<mi[now][1] && mi[x][1]+road[q][2]>mi[now][0])
{
fin[now]=0;
mi[now][1]=mi[x][1]+road[q][2];
mi[now][3]=x;
}
else if(mi[x][1]+road[q][2]<mi[now][0])
{
if(x==mi[now][2])mi[now][0]=mi[x][1]+road[q][2];
else
{
fin[now]=0;
mi[now][1]=mi[now][0];
mi[now][3]=mi[now][2];
mi[now][0]=mi[x][1]+road[q][2];
mi[now][2]=x;
}
}
}
q=road[q][1];
}
fin[t[pp]]=1;
pp++;
}
return mi[0][1];
}
