#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<vector<pair<int, int>>> tree;
vector<ll> dp;
void dfs(int node, int p = 0) {
for (auto [nxt, w]: tree[node]) {
if (nxt == p) continue;
dfs(nxt, node);
}
vector<ll> chDp;
for (auto [nxt, w]: tree[node]) if (nxt != p) chDp.push_back(dp[nxt] + w);
if (chDp.empty()) return;
sort(chDp.begin(), chDp.end());
dp[node] = chDp[1];
}
int travel_plan(int N, int M, int r[][2], int l[], int k, int p[]) {
n = N;
tree.clear();
tree.resize(n);
for (int i = 0; i < n-1; i++) {
int u = r[i][0];
int v = r[i][1];
int w = l[i];
tree[u].push_back({v, w});
tree[v].push_back({u, w});
}
dp.assign(n, 0);
dfs(0);
return (int)dp[0];
}
