#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++)
#define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define szx(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define mod 1000000007
using namespace std;
// void solve() {
// cin >> n;
// FOR(i, 1, n) cin >> a[i];
// FOR(i, 1, n) cin >> b[i];
// FOR(i, 1, 51) allowed[i] = 1;
// ll ans = 0;
// ROF(k, 51, 1) {
// allowed[k] = 0;
// FOR(i, 1, n) {
// bool ok = 1;
// if (!bfs(a[i], b[i])) {
// ans += (1LL << k);
// allowed[k] = 1;
// ok = 0;
// break;
// }
// if (!ok) break;
// }
// }
// cout << (ans == ((1LL << 52) - 2) ? -1 : ans);
// }
// int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(nullptr);
// // freopen("main.in", "r", stdin);
// // freopen("main.out", "w", stdout);
// int t = 1;
// // cin >> t;
// while (t--) { solve(); }
// }
#include "crocodile.h"
#define inf (ll)1e18 + 7
const int MAX = 1e5 + 5;
vector<pii> g[MAX];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
REP(i, M) {
g[R[i][0] + 1].pb({R[i][1] + 1, L[i]});
g[R[i][1] + 1].pb({R[i][0] + 1, L[i]});
}
vector<ll> min1(N + 1, inf), min2(N + 1, inf);
priority_queue<pli, vector<pli>, greater<pli>> pq;
REP(i, K) min1[P[i] + 1] = min2[P[i] + 1] = 0, pq.push({0, P[i] + 1});
while (!pq.empty()) {
int u = pq.top().se;
ll d = pq.top().fi;
pq.pop();
if (d != min2[u]) continue;
for (pii p : g[u]) {
int v = p.fi;
int w = p.se;
if (d + w <= min1[v]) {
min2[v] = min1[v];
min1[v] = d + w;
if (min2[v] != inf) pq.push({min2[v], v});
} else if (d + w < min2[v]) {
min2[v] = d + w;
pq.push({min2[v], v});
}
}
}
return min2[1];
}
