#include "crocodile.h"
#include <functional>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF = 1E15;
const int MAXN = 100010;
vector<pair<int,int>> adj[MAXN];
int depths[MAXN];
int maxDepth = 0;
bool done[MAXN];
bool isExit[MAXN];
priority_queue<int, vector<int>, greater<>> values[MAXN];
void dfs(int node, int parent, int depth) {
depths[node] = depth;
maxDepth = max(depth, maxDepth);
for (auto [child, cost] : adj[node]) {
if (child == parent) continue;
dfs(child, node, depth+1);
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
for (int i = 0; i < K; i++) {
isExit[P[i]] = true;
values[P[i]].push(0);
values[P[i]].push(0);
}
for (int i = 0; i < M; i++) {
int a = R[i][0], b = R[i][1], c = L[i];
adj[a].emplace_back(b,c);
adj[b].emplace_back(a,c);
}
dfs(0, 0, 0);
vector<vector<int>> v(maxDepth+1, vector<int>());
for (int i = 0; i < N; i++) {
v[depths[i]].push_back(i);
}
for (int i = maxDepth; i >= 0; i--) {
for (int node : v[i]) {
if (values[node].size() < 2) continue;
values[node].pop();
int a = values[node].top();
for (auto [child, cost] : adj[node]) {
values[child].push(a+cost);
}
}
}
values[0].pop();
return values[0].top();
}
