#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int MAXN=1e5+5;
const int MMM=1e6+5;
const int oo=1e9+1;
int N,M,K,dist,u,x,y,z;
int R[MMM][2],L[MMM],P[MAXN],d[MAXN][2];
vector <pii> adj[MAXN];
priority_queue <pii,vector<pii>,greater<pii>> pq;
int travel_plan(int N,int M,int R[][2],int L[],int K,int P[])
{
auto dijkstra = [&](int goal)
{
while (!pq.empty()) pq.pop();
for (int i=0;i<N;i++)
d[i][0]=d[i][1]=oo;
for (int i=0;i<K;i++)
{
d[P[i]][0]=d[P[i]][1]=0;
pq.push(make_pair(0,P[i]));
}
while (!pq.empty())
{
dist=pq.top().X;
u=pq.top().Y;
pq.pop();
if (dist>d[u][1]) continue;
if (u==goal) return dist;
for (pii v:adj[u])
if (d[v.Y][0]>dist+v.X)
{
if (d[v.Y][1]!=d[v.Y][0])
{
d[v.Y][1]=d[v.Y][0];
pq.push(make_pair(d[v.Y][1],v.Y));
}
d[v.Y][0]=dist+v.X;
}
else if (d[v.Y][1]>dist+v.X)
{
d[v.Y][1]=dist+v.X;
pq.push(make_pair(d[v.Y][1],v.Y));
}
}
return d[goal][1];
};
for (int i=0;i<M;i++)
{
x=R[i][0];
y=R[i][1];
z=L[i];
adj[x].push_back(make_pair(z,y));
adj[y].push_back(make_pair(z,x));
}
return dijkstra(0);
}
