#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
#define fr first
#define sc second
#define pb emplace_back
const int mxN = 1005;
vector<pi> adj[mxN];
ll dp[mxN] = {};
void dfs(ll x, ll p) {
dp[x] = 0;
vi curr;
for(auto [i, w] : adj[x]) {
if(i == p) continue;
dfs(i, x);
curr.pb(dp[i] + w);
}
if(curr.empty()) return;
sort(curr.begin(), curr.end());
dp[x] = curr[1];
}
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]].pb(R[i][1], L[i]);
adj[R[i][1]].pb(R[i][0], L[i]);
}
dfs(0, -1);
return dp[0];
}
