#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define ll long long
#define ld long double
#define ui __int128_t
#define pb push_back
#define fi first
#define se second
const ll MOD3 = 1e9 + 7;
const ll MOD = 998244353;
const ll MOD2 = 676767677;
const ll inf = 1e18;
const ll infs = 1e12;
/********* DEBUG *********/
template<typename T>
struct is_vector : false_type {};
template<typename T, typename A>
struct is_vector<vector<T, A>> : true_type {};
template<typename T>
void print_one(const T& x) {
if constexpr (is_vector<T>::value) {
for (size_t i = 0; i < x.size(); i++) {
cout << x[i];
if (i + 1 < x.size()) cout << ' ';
}
} else {
cout << x;
}
}
template<typename... Args>
void out(const Args&... args) {
bool first = true;
auto print_arg = [&](const auto& v) {
if (!first) cout << ' ';
first = false;
print_one(v);
};
(print_arg(args), ...);
cout << endl;
}
/********* DEBUG *********/
/********* TEMPS *********/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
static inline ll splix(ll x) {
x += 0x9e3779b97f4a7c15ULL;
ll z = x;
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
return z ^ (z >> 31);
}
/********* TEMPS *********/
#include "crocodile.h"
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<pair<ll,ll>> val(N, {inf, inf});
vector<vector<pair<ll,ll>>> adj(N);
for (int i = 0; i < M; i++) {
adj[R[i][0]].pb({R[i][1], L[i]});
adj[R[i][1]].pb({R[i][0], L[i]});
}
for (int i = 0; i < K; i++) {
val[P[i]] = {0, 0};
}
set<pair<ll,ll>> pq;
for (int i = 0; i < N; i++) {
pq.insert({val[i].se, i});
}
vector<bool> seen(N);
while (pq.size()) {
auto [dist, u] = *pq.begin();
pq.erase({dist, u});
seen[u] = 1;
for (auto &[v, w] : adj[u]) {
if (seen[v]) continue;
ll nw = w + dist;
ll oldv = val[v].se;
pq.erase({oldv, v});
chmin(val[v].se, nw);
if (val[v].fi > val[v].se)
swap(val[v].fi, val[v].se);
pq.insert({val[v].se, v});
}
// out("dist, u:", dist, u);
}
// for (int i = 0; i < N; i++) {
// out("i, val:", i, val[i].fi, val[i].se);
// }
return val[0].se;
}
