#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
using ll = long long;
const int N=1000;
const ll inf=1e18;
vector<pair<int,int>>graph[N+1];
ll dfs(int u,int p){
ll cur;
pair<ll,ll>mn={inf,inf};
for(auto&i:graph[u])if(i.first!=p){
cur=dfs(i.first,u)+i.second;
if(mn.first>=cur){
mn.second=mn.first;
mn.first=cur;
}
else if(mn.second>=cur)mn.second=cur;
}
if(mn.second==inf)mn.second=0;
return mn.second;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
int u,v;
for(int i=0;i<M;++i){
u=R[i][0];v=R[i][1];
graph[u].push_back({v,L[i]});
graph[v].push_back({u,L[i]});
}
return dfs(0,0);
}
