#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 2e6 + 5;
using namespace std;
vector<vector<pii>> v;
ll dist[mxN], mn[mxN];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
memset(mn, -1, sizeof mn);
v.resize(N + 2);
for (ll i = 0; i < N; i++)
{
dist[i] = 1e9 + 5;
}
for (ll i = 0; i < M; i++)
{
v[R[i][1]].push_back({R[i][0], L[i]});
v[R[i][0]].push_back({R[i][1], L[i]});
}
priority_queue<pii, vector<pii>, greater<pii>> q;
for (ll i = 0; i < K; i++)
{
dist[P[i]] = 0;
q.push({0, P[i]});
}
while (q.size())
{
auto u = q.top();
q.pop();
if (dist[u.S] < u.F)
continue;
for (auto x : v[u.S])
{
if (dist[x.F] > x.S + u.F && mn[x.F] == -1)
{
mn[x.F] = x.S + u.F;
}
else if (dist[x.F] > x.S + u.F && mn[x.F] != -1)
{
ll Mn = mn[x.F];
mn[x.F] = min(x.S + u.F, Mn);
dist[x.F] = max(x.S + u.F, Mn);
q.push({dist[x.F], x.F});
}
}
}
return dist[0];
}
