#include <bits/stdc++.h>
using namespace std;
#define ll long long
#include "crocodile.h"
const ll INF = 1e18;
struct twoSet{
ll x = INF, y = INF; // x < y
bool insert(ll v){
if(v >= y) return false;
y = v;
if(x > y) swap(x, y);
return true;
}
ll get(){ return y; }
};
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<twoSet> dist(N);
vector<pair<int, ll>> g[N];
for(int i=0; i<M; ++i){
g[R[i][0]].emplace_back(R[i][1], L[i]);
g[R[i][1]].emplace_back(R[i][0], L[i]);
}
priority_queue<pair<ll, int>> q;
for(int i=0; i<K; ++i){
q.emplace(0, P[i]);
dist[P[i]].insert(0);
dist[P[i]].insert(0);
}
while(!q.empty()){
ll u = q.top().second, d = -q.top().first; q.pop();
if(d != dist[u].get()) continue;
for(auto &e : g[u]){
ll v = e.first, w = e.second;
if(dist[v].insert(d + w)) q.emplace(-dist[v].get(), v);
}
}
return dist[0].get();
}
