#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define tY template<typename T
tY> using vec = vector<T>;
tY> using maxheap = priority_queue<T>;
tY> using minheap = priority_queue<T,vec<T>,greater<T>>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define fi first
#define se second
#define sp << " "
#define sps << " " <<
#define nl << endl
#define all(a) a.begin(),a.end()
ll min(vll &a) { return *min_element(all(a)); }
ll max(vll &a) { return *max_element(all(a)); }
ll sum(vll &a) { return accumulate(all(a),0ll); }
void sort(vll &a) { sort(all(a)); }
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
ll n = N, m = M;
vec<vec<pll>> adj(n);
vec<bool> ending(n,0);
for(int i = 0; i < m; i++) {
ll u = R[i][0], v = R[i][1];
adj[u].pb({v,L[i]});
adj[v].pb({u,L[i]});
}
vll dists(n,1e18), parent(n,-1);
minheap<pll> pq;
for(int i = 0; i < K; i++) {
ll u = P[i];
ending[P[i]] = 1;
pq.push({0,u});
dists[u] = 0;
}
while(!pq.empty()) {
auto [d,u] = pq.top();
pq.pop();
if(d > dists[u]) continue;
for(auto[v,w] : adj[u]) {
if(d+w < dists[v]) {
dists[v] = d+w;
pq.push({d+w,v});
parent[v] = u;
}
}
}
// cerr << "Multisource done" << endl;
dists.assign(n,1e18); // Lol!
dists[0] = 0;
pq.push({0,0});
while(!pq.empty()) {
auto [d,u] = pq.top();
if(ending[u]) break;
// cerr << u << endl;
pq.pop();
if(d > dists[u]) continue;
for(auto[v,w] : adj[u]) {
if(v == parent[u]) continue;
if(d+w < dists[v]) {
dists[v] = d+w;
pq.push({d+w,v});
// parent[v] = u;
}
}
}
// cerr << "Parents: " sp;
// for(ll &x : parent) cerr << x sp;
// cerr nl;
// cerr << "Dists: " sp;
// for(ll &x : dists) cerr << x sp;
// cerr nl;
ll mn = 1e18;
for(int i = 0; i < n; i++) {
if(ending[i]) mn = min(mn,dists[i]);
}
return mn;
}
