#include <bits/stdc++.h>
#include "race.h"
using ll =long long;
//#define int ll
ll LINF=1000000000000000000;
int INF=1e9;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>
//#define int ll
using namespace std;
vector<vector<pi>>g;
int k;
int minimum=INF;
vi vinf={INF,-1};
void add(vector<vii>&v,vector<vii>&cv,int node,int dist){
for(int i=0;i+dist<k+1;i++){
if(v[i+dist][0][0]>cv[i][1][0]+1){
v[i+dist][0][0]=cv[i][1][0]+1;
v[i+dist][0][1]=node;
if(v[i+dist][0][0]<v[i+dist][1][0]){
swap(v[i+dist][0][0],v[i+dist][1][0]);
swap(v[i+dist][0][1],v[i+dist][1][1]);
}
}
}
}
vector<vii> dfs(int node,int parent){
vector<vii>v(k+1,vii(2,vi({INF,-1})));
v[0][0]={0,node};
for(pi child:g[node]){
if(child.first==parent)continue;
auto cv=dfs(child.first,node);
add(v,cv,child.first,child.second);
}
for(int i=0;i<k+1;i++){
if(v[i][1][0]!=INF){
if(v[k-i][1][0]!=INF){
if(v[k-i][1][1]!=v[i][1][1]){
minimum=min(minimum,v[k-i][1][0]+v[i][1][0]);
}
else {
minimum=min(minimum,v[k-i][0][0]+v[i][1][0]);
}
}
}
}
return v;
}
int best_path(int N, int K, int H[][2], int L[])
{
g.resize(N);
k=K;
for(int i=0;i<N-1;i++){
g[H[i][0]].push_back(make_pair(H[i][1],L[i]));
g[H[i][1]].push_back(make_pair(H[i][0],L[i]));
}
dfs(0,-1);
if(minimum==1e9)return -1;
return minimum;
}
