#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using aa = array<int,3>;
using ii = pair<int,int>;
const int N = 1e5+5;
const int MOD = 1e9+7;
int v, u, kc, d[N][2];
bool vis[N];
vector <ii> adj[N];
priority_queue<ii,vector<ii>,greater<ii>> pq;
signed travel_plan(signed N,signed M,signed R[][2],signed L[],signed K,signed P[]){
for (int i = 0; i < M; i++){
R[i][0]++;
R[i][1]++;
adj[R[i][0]].push_back({R[i][1],L[i]});
adj[R[i][1]].push_back({R[i][0],L[i]});
}
for (int i = 1; i <= N; i++){
d[i][0] = 1e18;
d[i][1] = 1e18;
}
for (int i = 0; i < K; i++){
P[i]++;
d[P[i]][0] = d[P[i]][1] = 0;
pq.push({0,P[i]});
}
while (!pq.empty()){
tie(kc,u) = pq.top();
pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (ii it : adj[u]){
v = it.fi;
int tmp = kc + it.se;
if (tmp < d[v][1]){
d[v][1] = tmp;
if (d[v][0] > d[v][1]) swap(d[v][0],d[v][1]);
pq.push({d[v][1],v});
}
}
}
return d[1][1];
}
