#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=1000+5;
ll isexit[mxn],col[mxn],n,m,arr[mxn];
vector<pll>vt[mxn];
ll funk(int u,ll sum,int cut,vector<int>color){
if(arr[u]<sum){
return INF;
}
color[u]=1;
arr[u]=min(arr[u],sum);
if(isexit[u]){
return sum;
}
ll ans=0;
if(cut==-1){
for(int i=0;i<vt[u].size();i++){
if(!color[vt[u][i].F]){
ans=max(ans,funk(u,sum,i,color));
}
}
return ans;
}
else{
ll x=INF;
for(int i=0;i<vt[u].size();i++){
if(i!=cut&&!color[vt[u][i].F]){
x=min(funk(vt[u][i].F,sum+vt[u][i].S,-1,color),x);
}
}
return x;
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
n=N,m=M;
for(int i=0;i<m;i++){
vt[R[i][0]].pb({R[i][1],L[i]});
vt[R[i][1]].pb({R[i][0],L[i]});
}
for(int i=0;i<K;i++){
isexit[P[i]]=1;
}
vector<int>vv;
for(int i=0;i<=n;i++){
vv.pb(0);
arr[i]=INF;
}
ll ans=funk(0,0,-1,vv);
return ans;
}
