#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>
using namespace std;
struct edg
{
int x;
long long w;
bool operator <(const edg &a) const
{
return w > a.w;
}
};
vector<edg> arr[100010];
edg dis[100010][2];
long long INF = 1e15;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int i = 0; i < M; i++)
{
int x = R[i][0];
int y = R[i][1];
int w = L[i];
arr[x].push_back({ y, w });
arr[y].push_back({ x, w });
}
for(int i = 0; i < N; i++)
dis[i][0] = dis[i][1] = { i, INF };
priority_queue<edg> pq;
for(int i = 0; i < K; i++)
{
int x = P[i];
dis[x][0] = dis[x][1] = { x, 0 };
pq.push({ x, 0 });
}
while(!pq.empty())
{
int x = pq.top().x;
long long w = pq.top().w;
pq.pop();
if(w > dis[x][1].w)
continue;
for(edg e : arr[x])
{
long long nw = w + e.w;
if(nw < dis[e.x][0].w && x != dis[e.x][0].x)
{
dis[e.x][1] = dis[e.x][0];
dis[e.x][0] = { x, nw };
if(dis[e.x][1].w != INF)
pq.push({ e.x, dis[e.x][1].w });
}
else if(nw < dis[e.x][1].w && x != dis[e.x][1].x)
{
dis[e.x][1] = { x, nw };
if(dis[e.x][1].w != INF)
pq.push({ e.x, dis[e.x][1].w });
}
}
}
assert(dis[0][1].w != INF);
return dis[0][1].w;
}
