#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define ll int
#define li pair <ll, int>
#define fi first
#define se second
const int N = 1e5 + 10;
// const int M = 1e6 + 10;
const ll INF = 2e9;
// int n, m, r[M][2], l[M], k, p[N];
ll dis[N][2];
vector <li> v[N];
priority_queue < li, vector <li>, greater <li> > q;
bool opt(int u, ll val) {
if (dis[u][0] > val) {
dis[u][1] = dis[u][0];
dis[u][0] = val;
if (dis[u][1] != INF) return true;
return false;
}
if (dis[u][1] > val) {
dis[u][1] = val;
return true;
}
return false;
}
ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
for (int i = 0; i < M; ++i) {
v[R[i][0]].push_back(li(L[i], R[i][1]));
v[R[i][1]].push_back(li(L[i], R[i][0]));
}
for (int i = 0; i < N; ++i) {
dis[i][0] = dis[i][1] = INF;
}
for (int i = 0; i < K; ++i) {
dis[P[i]][0] = dis[P[i]][1] = 0;
q.push(li(0, P[i]));
}
while (!q.empty()) {
li p = q.top(); q.pop();
ll w = p.fi;
int u = p.se;
if (u == 0) return w;
if (w > dis[u][1]) continue;
for (li z: v[u]) {
if (opt(z.se, w + z.fi)) {
q.push(li(dis[z.se][1], z.se));
}
}
}
return INF;
}
// int main() {
// freopen("input.txt", "r", stdin);
// cin.tie(0); cout.tie(0);
// ios_base::sync_with_stdio(false);
// cin >> n >> m;
// for (int i = 1; i <= m; ++i) {
// cin >> r[i][0] >> r[i][1];
// }
// for (int i = 1; i <= m; ++i) cin >> l[i];
// cin >> k;
// for (int i = 1; i <= k; ++i) cin >> p[i];
// cout << travel_plan(n, m, r, l, k, p);
// return 0;
// }
