#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define MAX 100000
#define des first
#define peso second
lli n,m,a,b,res;
vector<pair<lli,lli> > hijos[MAX+2];
lli visitados[MAX+2];
set<pair<lli,lli> > cola;
set<pair<lli,lli> >::iterator it;
pair<lli,lli> act;
multiset<lli> llegadas[MAX+2];
multiset<lli>::iterator ot;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
n = N;
m = M;
rep(i,0,m-1) {
a = R[i][0];
b = R[i][1];
hijos[a].push_back({b,L[i]});
hijos[b].push_back({a,L[i]});
}
rep(i,0,K-1) {
a = P[i];
cola.insert({0,a});
}
while (!cola.empty()) {
it = cola.begin();
act = (*it);
cola.erase(it);
if (visitados[act.second] == 1) continue;
visitados[act.second] = 1;
if (act.second == 0) {
res = act.first;
break;
}
for (auto h : hijos[act.second]) {
if (visitados[h.des] == 1) continue;
a = act.first + h.peso;
llegadas[h.des].insert(a);
if (llegadas[h.des].size() > 1) {
ot = llegadas[h.des].begin();
ot++;
a = (*ot);
if (cola.find({a,h.des}) == cola.end()) cola.insert({a,h.des});
}
}
}
return res;
}
