#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "grader.cpp"
#endif // LOCAL
#define forr(x,i,n) for(int x=i; x<n; x++)
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define fi first
#define se second
bool vis[100000];
bool ex[100000];
int routes[100000];
vector<pii> a[100000];
//vector<pii> dp[100000];
int dfs(int x)
{
if (ex[x])
{
return 0;
}
if (routes[x]!=0) return routes[x];
int ch1=INT_MAX, ch2=INT_MAX;
for(auto y:a[x])
{
if (!vis[y.fi])
{
vis[y.fi]=1;
int ch=(dfs(y.fi))+y.se;
if (ch<=ch1 && ch<=ch2)
{
ch2=ch1;
ch1=ch;
}
else if (ch>=ch1 && ch<=ch2)
{
ch2=ch;
}
vis[y.fi]=0;
}
}
//sort(all(ch));
return routes[x]=ch2;
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int e[])
{
//r/l/k/e/
forr(i,0,m)
{
int x=r[i][0];
int y=r[i][1];
a[x].pb({y,l[i]});
a[y].pb({x,l[i]});
// dp[x].pb(0);
// dp[y].pb(0);
}
forr(i,0,k) ex[e[i]]=1;
vis[0]=1;
return dfs(0);
}
