#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
int dpf[maxn], dps[maxn];
vector<pair<int,int> > g[maxn];
void dfs(int node, int p) {
if(g[node].size() == 1) {
dps[node] = dpf[node] = 0LL;
return;
}
vector<ll>dp;
for(auto i:g[node]) {
if(i.first != p) {
dfs(i.first, node);
dp.pb(dps[i.first] + i.second);
}
}
sort(dp.begin(), dp.end());
if(g[node].size() == 1) return;
dpf[node] = dp[0];
dps[node] = dp[1];
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
for(int i=0;i<M;i++) {
g[R[i][0]].pb(mp(R[i][1], L[i]));
g[R[i][1]].pb(mp(R[i][0], L[i]));
}
dfs(0, -1);
return int(dps[0]);
}
