#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)9e18;
ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<vector<pair<int,ll>>> adj(N);
for(int i=0;i<M;i++){
int u = R[i][0];
int v = R[i][1];
ll w = L[i];
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
// best1[u] = smallest candidate = min_{neighbor x} (L(u,x) + T_x)
// best2[u] = second smallest candidate -> T_u = best2[u]
vector<ll> best1(N, INF), best2(N, INF);
// min-heap of (candidateDistance, node) ordered by candidateDistance
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
// exits: T_exit = 0. We treat that by pushing candidate 0 for the exit itself
for(int i=0;i<K;i++){
int u = P[i];
// push a candidate "0" coming from the exit concept
// we set both best1 and best2 to 0 so that edges adjacent to exit
// will see L + 0 as candidates.
if (best1[u] > 0) {
best2[u] = best1[u];
best1[u] = 0;
pq.push({best1[u], u});
} else if (best2[u] > 0) {
best2[u] = 0;
pq.push({best2[u], u});
}
}
// Note: we will propagate candidates: when we pop (d,u) equal to best2[u] (the second smallest),
// we relax neighbors v with candidate = d + L(u,v).
while(!pq.empty()){
auto [cur, u] = pq.top(); pq.pop();
// we only process when cur equals best2[u] (we want process nodes whose second-best settled)
if (cur != best2[u]) continue;
for(auto [v, w] : adj[u]){
ll cand = cur + w; // L(v,u) + T_u (we popped T_u as best2[u] = cur)
// Insert cand into v's two-best structure
if (cand < best1[v]){
best2[v] = best1[v];
best1[v] = cand;
// whenever best2 improved (could be INF->value or decreased), push it
if (best2[v] < INF) pq.push({best2[v], v});
} else if (cand < best2[v]){
best2[v] = cand;
if (best2[v] < INF) pq.push({best2[v], v});
}
}
}
// The answer is T_0 = best2[0]
return best2[0];
}
