#include <bits/stdc++.h>
#include "crocodile.h"
#define ii pair < int , int >
#define fi first
#define se second
using namespace std;
vector < ii > vec[1005];
long long dp[1005];
void dfs(int u , int p)
{
long long mn1,mn2;
mn1=mn2=1e9+7;
int v,c;
for(auto x:vec[u])
{
v=x.fi;
c=x.se;
if(v==p)
continue ;
dfs(v,u);
if(mn2>dp[v]+c)
mn2=dp[v]+c;
if(mn1>mn2)
swap(mn1,mn2);
}
dp[u]=mn2;
if(vec[u].size()==1)
dp[u]=0;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int i=0;i<M;i++)
{
vec[R[i][1]].push_back({R[i][0],L[i]});
vec[R[i][0]].push_back({R[i][1],L[i]});
}
dfs(0,0);
return dp[0];
}
