#include "crocodile.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define nmax 100008
const long long inf = 1e18;
using namespace std;
typedef pair<long long, long long> pii;
pii operator+(pii x, long long y){
return (y <= x.fi) ? make_pair(y, x.fi) : ((y < x.se) ? make_pair(x.fi, y) : x);
}
int n, m;
bool kt[nmax];
pii f[nmax];
vector<pii> l[nmax];
typedef pair<pii, int> ppiii;
struct cmp{
bool operator()(ppiii x, ppiii y){
return x.fi.se > y.fi.se;
}
};
priority_queue<ppiii, vector<ppiii>, cmp> s;
bool check(pii x, pii y){
return (x.se != y.se) ? (x.se > y.se) : (x.fi > y.fi);
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
n = N;
m = M;
fill(f, f + n + 1, make_pair(inf, inf));
for (int i = 0; i < m; i++){
int u = R[i][0], v = R[i][1], w = L[i];
l[u].push_back({v, w});
l[v].push_back({u, w});
}
for (int i = 0; i < K; i++){
f[P[i]] = {0, 0};
s.push({f[P[i]], P[i]});
}
while (!s.empty()){
int u = s.top().se;
pii val = s.top().fi;
s.pop();
if (f[u] != val)
continue;
if (!u)
break;
for (pii it : l[u]){
ppiii v = {f[it.fi] + (val.se + it.se), it.fi};
if (check(f[v.se], v.fi)){
f[v.se] = v.fi;
s.push(v);
}
}
}
return f[0].se;
}
