#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const int NNN = 1e5 + 5;
long long dist1[NNN], dist2[NNN];
vector<pair<int, int>> vec[NNN];
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
for(int i = 0; i < n; i++)
dist1[i] = dist2[i] = 1e12;
for(int i = 0; i < m; i++)
{
int u = R[i][0], v = R[i][1], w = L[i];
vec[u].push_back({v, w});
vec[v].push_back({u, w});
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for(int i = 0; i < K; i++)
{
q.push({0, P[i]});
dist1[P[i]] = dist2[P[i]] = 0;
}
while(!q.empty())
{
long long node = q.top().second, dst = q.top().first;
q.pop();
if(dst > dist2[node])
continue;
for(auto p : vec[node])
{
long long to = p.first, w = p.second;
if(dst + w < dist1[to])
{
if(dist1[to] < dist2[to])
{
dist2[to] = dist1[to];
dist1[to] = dst + w;
q.push({dist2[to], to});
}
else
{
dist2[to] = dist1[to];
dist1[to] = dst + w;
}
}
else if(dst + w < dist2[to])
{
dist2[to] = dst + w;
q.push({dist2[to], to});
}
}
}
return dist2[0];
}
