#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pr pair <int, int>
using namespace std;
const int N = 1e5 + 5;
int n, m, r, val[N], tmp[N];
vector <pr> a[N];
int d[N][2];
int e[N][2], W[N];
bool vis[N];
//void inp()
//{
// cin >> n >> m >> r;
// for (int i = 0; i < m; i++)
// {
// int x, y;
// ll w;
// cin >> e[i][0] >> e[i][1];
// }
// for (int i = 0; i < m; i++)
// cin >> W[i];
// for (int i = 0; i < r; i++)
// {
// cin >> tmp[i];
// }
//}
void dijkstra ()
{
priority_queue <pr, vector <pr>, greater <pr>> q;
memset(d, 0x3f, sizeof(d));
memset(vis, false, sizeof(vis));
for (int i = 1; i <= r; i++)
{
q.push({0, val[i]});
d[val[i]][0] = d[val[i]][1] = 0;
}
while (!q.empty())
{
int u = q.top().se;
ll k = q.top().fi;
q.pop();
if (vis[i])
continue;
vis[i] = true;
for (pr i : a[u])
{
int v = i.se;
ll sum = k + i.fi;
if (sum < d[v][0])
{
d[v][1] = d[v][0];
d[v][0] = sum;
q.push({d[v][1], v});
}
else if (sum < d[v][1])
{
d[v][1] = sum;
q.push({d[v][1], v});
}
}
}
}
//void solve()
//{
// dijkstra();
// cout << d[1][1];
//}
ll travel_plan (int N, int M, int R[][2], int L[], int K, int P[])
{
n = N;
m = M;
r = K;
for (int i = 0; i < m; i++)
{
//cout << L[i] << " ";
a[R[i][0]+1].push_back({L[i], R[i][1]+1});
a[R[i][1]+1].push_back({L[i], R[i][0]+1});
}
for (int i = 0; i < K; i++)
val[i+1] = P[i] + 1;
dijkstra();
return d[1][1];
}
//int main()
//{
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("TEST.INP","r",stdin);
// freopen("TEST.OUT","w",stdout);
// inp();
// cout << travel_plan(n, m, e, W, r, tmp);
//}
