#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define sep ' '
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
ll dist[MAXN], n, m;
set<pll> adj_st[MAXN], adj_st_r[MAXN];
vector<pll> adj[MAXN];
priority_queue<pll, vector<pll>, greater<pll>> pq;
inline void check(int v) {
if (int(adj_st[v].size()) > 1 && (next(adj_st[v].begin()) -> X) < dist[v]) {
dist[v] = next(adj_st[v].begin()) -> X;
pq.push({dist[v], v});
}
}
inline void fix(int v) {
for (auto [u, l] : adj[v]) {
auto it = adj_st_r[u].lower_bound(pll(v, -1));
if (it != adj_st_r[u].end() && it -> X == v) {
ll d = it -> Y;
adj_st_r[u].erase(it);
adj_st[u].erase(pll(d, v));
}
adj_st_r[u].insert({v, dist[v] + l});
adj_st[u].insert({dist[v] + l, v});
check(u);
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
n = N, m = M;
for (int i = 0; i < m; i++) {
adj[R[i][0]].push_back({R[i][1], L[i]});
adj[R[i][1]].push_back({R[i][0], L[i]});
}
memset(dist, 63, sizeof dist);
for (int i = 0; i < K; i++) {
int v = P[i];
dist[v] = 0;
pq.push({0, v});
}
while (!pq.empty()) {
auto [d_v, v] = pq.top();
pq.pop();
if (d_v != dist[v]) continue;
if (v == 2) {
}
fix(v);
}
return dist[0];
}
