#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define plii pair<ll, pii>
#define pli pair<ll, int>
#include "crocodile.h"
using namespace std;
const ll INF = 1e15;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
vector<vector<pii>> graph(N);
vector<bool> exit(N, false);
int end = P[0];
for (int k = 0; k < K; k++)
exit[P[k]] = true;
for (int i = 0; i < M; i++)
{
if (exit[R[i][0]] && exit[R[i][1]])
continue;
if (exit[R[i][0]])
{
graph[end].push_back({R[i][1], L[i]});
graph[R[i][1]].push_back({end, L[i]});
}
else if (exit[R[i][1]])
{
graph[end].push_back({R[i][0], L[i]});
graph[R[i][0]].push_back({end, L[i]});
}
else
{
graph[R[i][0]].push_back({R[i][1], L[i]});
graph[R[i][1]].push_back({R[i][0], L[i]});
}
}
vector<vector<ll>> dist(N, vector<ll>(2, INF));
dist[end][0] = dist[end][1] = 0;
priority_queue<pli, vector<pli>, greater<pli>> q;
q.push({0, end});
while (!q.empty())
{
ll w;
int v;
tie(v, w) = q.top();
q.pop();
if (dist[v][1] < w)
continue;
for (pli e : graph[v])
{
ll wei;
int u;
tie(u, wei) = e;
if (dist[u][1] <= w + wei)
continue;
if (dist[u][0] > w + wei)
{
if (dist[u][0] < INF)
q.push({dist[u][0], u});
dist[u][1] = dist[u][0];
dist[u][0] = w + wei;
}
else if (dist[u][1] > w + wei)
{
dist[u][1] = w + wei;
q.push({w + wei, u});
}
}
}
return dist[0][1];
}
