#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e3+5;
ll dp[nx];
vector<vector<pair<ll, ll>>> d(nx);
void dfs(int u, int p)
{
ll mn1(LLONG_MAX), mn2(LLONG_MAX);
for (auto [v, w]:d[u])
{
if (v==p) continue;
dfs(v, u);
if (dp[v]+w<mn1) swap(mn1, mn2), mn1=dp[v]+w;
else if (dp[v]+1<mn2) mn2=dp[v]+w;
}
dp[u]=(d[u].size()==1)?0:mn2;
//cout<<u<<' '<<dp[u]<<'\n';
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for (int i=0; i<M; i++) d[R[i][0]].push_back({R[i][1], L[i]}), d[R[i][1]].push_back({R[i][0], L[i]});
dfs(0, 0);
return dp[0];
}
