#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
//#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
set<pair<ll,ll> >v[200010];
ll mi=1e9;
ll KK;
vector<ll> dim(200010),up(200010);
ll dfs(ll pos,ll prec){
up[pos]=prec;
dim[pos]++;
for(auto x:v[pos])if(x.first!=prec)dim[pos]+=dfs(x.first,pos);
return dim[pos];
}
map<ll,ll> best;
void w(ll pos,ll prec,ll dist,ll archi){
if(best.count(dist)==0 || archi<best[dist])best[dist]=archi;
for(auto k:v[pos]){
if(k.first==prec)continue;
w(k.first,pos,dist+k.second,archi+1);
}
}
void calcola(ll pos){
map<ll,ll> q;
for(auto k:v[pos]){
best.clear();
w(k.first,pos,k.second,1);
for(auto x:best){
if(q.count(KK-x.first)){
mi=min(mi,q[KK-x.first]+x.second);
}
if(x.first==KK){
mi=min(mi,x.second);
}
}
for(auto x:best){
if(q.count(x.first)==0 || x.second<q[x.first])q[x.first]=x.second;
}
}
//cout<<"calcolato: "<<pos<<" "<<mi<<endl;
}
void centroid(ll pos);
void trova(ll pos,ll nodi){
if(nodi==1)return;
for(auto k:v[pos]){
if(k.first==up[pos])continue;
if(dim[k.first]>nodi/2){
trova(k.first,nodi);
return;
}
}
calcola(pos);
vector<ll> vicini;
for(auto k:v[pos]){
if(v[k.first].find({pos,k.second})!=v[k.first].end())v[k.first].erase({pos,k.second});
vicini.push_back(k.first);
if(k.first!=up[pos])up[k.first]=-1;
}
v[pos].clear();
ll g=up[pos];
while(g!=-1){
dim[g]-=dim[pos];
g=up[g];
}
//cout<<"pulito: "<<pos<<endl;
up[pos]=-1;
for(ll x:vicini){
centroid(x);
}
}
void centroid(ll pos){
//cout<<"centroid: "<<pos<<" ";
while(up[pos]!=-1){
pos=up[pos];
}
//cout<<pos<<endl;
trova(pos,dim[pos]);
}
int best_path(int N, int K, int H[][2], int L[]){
for(ll i=0;i<N-1;i++){
v[H[i][0]].insert({H[i][1],L[i]});
v[H[i][1]].insert({H[i][0],L[i]});
}
KK=K;
dfs(0,-1);
centroid(0);
if(mi==1e9)return -1;
else return mi;
}
