#include "crocodile.h"
#include <vector>
using namespace std;
vector<int> vals;
vector<vector<pair<int,int>>> adjlist;
int dfs(int curr, int prev)
{
if (vals[curr] != -1) return vals[curr];
vals[curr] = 1e9;
int fr = 1e9;
int sec = 1e9;
for (auto p : adjlist[curr])
{
int next = p.first;
if (next == prev) continue;
int val = dfs(next, curr) + p.second;
if (val <= fr)
{
sec = fr;
fr = val;
}
else if (val <= sec)
{
sec = val;
}
}
return vals[curr] = sec;
}
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
vals.resize(n, -1);
for (int i = 0; i < k; i++)
{
vals[P[i]] = 0;
}
adjlist.resize(n);
for (int i = 0; i < m; i++)
{
adjlist[R[i][0]].push_back({R[i][1], L[i]});
adjlist[R[i][1]].push_back({R[i][0], L[i]});
}
return dfs(0, -1);
}
