#include "crocodile.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
static const int N = 100'010;
static const int inf = 1e9;
static vector<pii> A[N];
static set<pii> adj[N];
static int dis[N];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
Loop (i,0,m) {
A[r[i][0]].push_back({r[i][1], l[i]});
A[r[i][1]].push_back({r[i][0], l[i]});
}
fill (dis, dis+N, inf);
set<pii> s;
Loop (i,0,k) {
dis[p[i]] = 0;
s.insert({0, p[i]});
}
Loop (_,0,n) {
Loop (v,0,n) {
if (dis[v] == 0)
continue;
int vc[2] = {inf, inf};
for (auto [u, w] : A[v]) {
if (vc[1] > dis[u] + w)
vc[1] = dis[u] + w;
if (vc[0] > vc[1])
swap(vc[0], vc[1]);
}
dis[v] = vc[1];
}
}
return dis[0];
while (s.size()) {
auto [d, v] = *s.begin();
s.erase(s.begin());
for (auto [u, w] : A[v]) {
adj[u].insert({d + w, u});
int d2 = adj[u].size() >= 2? (++adj[u].begin())->first: inf;
if (d2 < dis[u]) {
s.erase({dis[u], u});
dis[u] = d2;
s.insert({dis[u], u});
}
}
}
return dis[0];
}
