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