#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
typedef long long ll;
int n;
vector<pair<int,ll>> g[100000];
ll dist[100000][2];
bool vis[100000];
void dijkstra(int K, int P[])
{
for (int i = 0; i < n; i++)
{
dist[i][0] = dist[i][1] = LLONG_MAX;
vis[i] = false;
}
priority_queue<pair<ll,int>> pq;
for (int i = 0; i < K; i++)
{
pq.push({0LL, P[i]});
dist[P[i]][0] = dist[P[i]][1] = 0LL;
}
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
for (auto [v, l] : g[u])
if (!vis[v])
if (dist[u][1] + l < dist[v][1])
{
dist[v][1] = dist[u][1] + l;
if (dist[v][1] < dist[v][0])
swap(dist[v][0], dist[v][1]);
if (dist[v][1] != LLONG_MAX)
pq.push({-dist[v][1], v});
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
n = N;
for (int i = 0; i < M; i++)
{
g[R[i][0]].push_back({R[i][1], L[i]});
g[R[i][1]].push_back({R[i][0], L[i]});
}
dijkstra(K, P);
return dist[0][1];
}
