#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int nax = 1005;
constexpr ll INF = 1e15+5;
vector<pair<int, int>> adj[nax];
ll dp[nax];
bool esc[nax];
void dfs(int v, int p=-1) {
if (esc[v]) {
return;
}
priority_queue<ll, vector<ll>, greater<ll>> q;
for(auto& u : adj[v]) {
if (p == u.first) continue;
dfs(u.first, v);
q.push(dp[u.first]+u.second);
}
if (q.size() >= 2) {
q.pop();
dp[v] = min(dp[v], q.top());
}
//cout << v << ": " << dp[v] << "\n";
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int i = 0; i < M; i++) {
adj[R[i][0]].push_back({R[i][1], L[i]});
adj[R[i][1]].push_back({R[i][0], L[i]});
}
for(int i = 0; i <= N; i++) {
dp[i] = INF;
}
for(int i = 0; i < K; i++) {
dp[P[i]] = 0;
esc[P[i]] = true;
}
dfs(0);
return dp[0];
}
