#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
const ll maxn = 100010;
ll dist1[maxn], dist2[maxn];
vector <pi> adjlist[maxn];
ll n, e;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
n = N; e = M;
for (ll i =0;i<e;i++) {
ll a = R[i][0], b = R[i][1], c = L[i];
adjlist[a].push_back(pi(b,c));
adjlist[b].push_back(pi(a,c));
}
priority_queue <pi, vector<pi>, greater<pi>> pq;
memset(dist1,-1,sizeof dist1);
memset(dist2,-1,sizeof dist2);
for (ll i =0;i<K;i++) {
pq.push(pi(0, P[i]));
dist1[P[i]] = dist2[P[i]] = 0;
}
while (!pq.empty()) {
auto [d, x] = pq.top(); pq.pop();
if (dist2[x] < d) continue;
for (auto [i, c]: adjlist[x]) {
if (dist1[i] == -1) {
dist1[i] = d + c;
} else if (dist2[i] == -1) {
dist2[i] = d + c;
if (dist2[i] < dist1[i]) swap(dist1[i], dist2[i]);
pq.push(pi(dist2[i], i));
} else if (d + c < dist2[i]) {
dist2[i] = d + c;
if (dist2[i] < dist1[i]) swap(dist1[i], dist2[i]);
pq.push(pi(dist2[i], i));
}
}
}
return dist2[0];
}
