#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> > > adjlist;
int INF = 100000000;
vector<bool> isEnd;
vector<bool> visited;
vector<int> dp;
int dfs(int x){
if (dp[x]!=-1){
return x;
}
//cout<<x<<endl;
visited[x]=true;
int min1 = INF;
int min2 = INF;
if (isEnd[x]){
visited[x]=false;
return dp[x]=0;
}
for (auto p : adjlist[x]){
if (visited[p.second]){
continue;
}
int distance = p.first+dfs(p.second);
if (distance<min1){
min2=min1;
min1=distance;
} else if (distance<min2){
min2=distance;
}
}
visited[x]=false;
return dp[x]=min2;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
adjlist.resize(N);
for (int i = 0; i<M; i++){
adjlist[R[i][0]].push_back(make_pair(L[i],R[i][1]));
adjlist[R[i][1]].push_back(make_pair(L[i],R[i][0]));
}
isEnd.resize(N,false);
visited.resize(N,false);
dp.resize(N,-1);
for (int i = 0; i<K; i++){
isEnd[P[i]]=true;
}
return dfs(0);
}
