#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int l=2e5+1;
vector<pair<int,int>> adj[l];
int n,k;
int ans;
bool used[l];
int cnt[l];
int num;
vector<int> p;
int mn(int x,int y){
if(x==-1){
return y;
}
return min(x,y);
}
void dfs(int node,int parent){
++num;
cnt[node]=1;
for(auto i:adj[node]){
if(i.first==parent){
continue;
}
if(used[i.first]){
continue;
}
dfs(i.first,node);
cnt[node]+=cnt[i.first];
}
}
bool center(int node,int parent){
for(auto i:adj[node]){
if(used[i.first])
continue;
if(i.first==parent){
continue;
}
if(cnt[i.first]>num/2){
return 0;
}
}
return 1;
}
int find_centroid(int node){
num=0;
dfs(node,-1);
if(num==1){
return -1;
}
int gag=node;
int parent=-1;
while(!center(gag,parent)){
for(auto i:adj[gag]){
if(used[i.first]){
continue;
}
if(i.first==parent){
continue;
}
if(cnt[i.first]>num/2){
parent=gag;
gag=i.first;
break;
}
}
}
used[gag]=1;
return gag;
}
map<int,int> mp;
vector<pair<int,int>> mas;
void dfsx(int node,int parent,int root,int her,int r){
if(node!=root){
mas.push_back({her,r});
auto it=mp.find(k-her);
if(it!=mp.end()){
ans=mn(ans,it->second+r);
}
}
for(auto i:adj[node]){
if(i.first==parent){
continue;
}
if(used[i.first]){
continue;
}
if(node==root){
dfsx(i.first,node,root,her+i.second,r+1);
auto it=mp.find(k);
if(it!=mp.end()){
ans=mn(ans,it->second);
}
for(auto j:mas){
auto itx=mp.find(j.first);
if(itx==mp.end()){
mp.insert({j.first,j.second});
}
else{
itx->second=min(itx->second,j.second);
}
}
mas.clear();
continue;
}
dfsx(i.first,node,root,her+i.second,r+1);
}
}
void solve_helper(int u){
mp.clear();
mp.insert({0,0});
dfsx(u,-1,u,0,0);
}
void solve(int node){
int u=find_centroid(node);
if(u==-1){
return ;
}
solve_helper(u);
for(auto i:adj[u]){
if(!used[i.first]){
solve(i.first);
}
}
//cout<<node<<" "<<u<<'\n';
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;
k=K;
ans=-1;
for(int i=0;i<n-1;++i){
adj[H[i][1]].push_back({H[i][0],L[i]});
adj[H[i][0]].push_back({H[i][1],L[i]});
}
solve(0);
return ans;
}
