#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> > > adjlist;
int INF = 100000000;
int dfs(int x, int parent){
int min1 = INF;
int min2 = INF;
if (adjlist[x].size()==1){
return 0;
}
for (auto p : adjlist[x]){
if (p.second==parent){
continue;
}
int distance = p.first+dfs(p.second,x);
if (distance<min1){
min2=min1;
min1=distance;
} else if (distance<min2){
min2=distance;
}
}
return min2;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
adjlist.resize(N);
for (int i = 0; i<M; i++){
adjlist[R[i][0]].push_back(make_pair(L[i],R[i][1]));
adjlist[R[i][1]].push_back(make_pair(L[i],R[i][0]));
}
return dfs(0,-1);
}
