#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn=2*1e5;
long long n,m;
struct edge
{
long long x,d;
edge(){}
edge(long long _x,long long _d)
{
x=_x;
d=_d;
}
bool operator<(const edge&e)const
{
return e.d<d;
}
};
vector<edge> v[maxn];
priority_queue<edge> q;
long long c[maxn],d[maxn];
void dijkstra()
{
for(long long i=0;i<n;i++)
if(c[i]==0)d[i]=1e18;
while(q.size())
{
edge t=q.top();
q.pop();
c[t.x]++;
if(c[t.x]!=2)
continue;
d[t.x]=t.d;
for(long long i=0;i<v[t.x].size();i++)
{
edge nb=v[t.x][i];
if(t.d+nb.d<=d[nb.x])
q.push({nb.x,nb.d+t.d});
}
}
}
void ae(long long i,long long j,long long x)
{
v[i].push_back({j,x});
v[j].push_back({i,x});
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
n=N;
m=M;
for(long long i=0;i<m;i++)
ae(R[i][0],R[i][1],L[i]);
for(long long i=0;i<K;i++)
{
c[P[i]]=1;
q.push({P[i],0});
}
dijkstra();
return d[0];
}
