#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std ;
const int N = 1010 ;
#define ff first
#define ss second
#define pb push_back
int dp[N];
vector <pair<int,int>> G[N] ;
const int oo = 1e9+2 ;
void go ( int u, int p ) {
int frMn = oo, scMn = (G[u].size()!=1)*oo;
for ( auto v:G[u] ) {
if ( p == v.ff ) continue ;
go ( v.ff, u ) ;
if ( dp[v.ff] + v.ss <= frMn ) scMn = frMn,frMn = dp[v.ff] + v.ss ;
else if ( dp[v.ff] + v.ss < scMn ) scMn = dp[v.ff] + v.ss ;
}
dp[u] = scMn ;
}
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 ( { R[i][1], L[i] } ), G[R[i][1]].pb({R[i][0],L[i]}) ;
go(0,-1);
return dp[0];
}
