#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MN=2e6+10;
long long n,k;
vector<int>r[MN];
vector<pair<int,long long>>r2[MN];
int br[MN];
bool vis[MN];
map<long long,int>hm;
int fans=INT_MAX;
void dfs(int x,int par){
br[x]=1;
for(auto p:r[x]){
if(p==par||vis[p])continue;
dfs(p,x);
br[x]+=br[p];
}
}
void dfs2(int x,int par,int de,long long pt){
if(pt>k)return;
if(k-pt!=0&&hm[k-pt]==0);
else fans=min(fans,hm[k-pt]+de);
for(auto p:r2[x]){
if(p.first==par||vis[p.first])continue;
dfs2(p.first,x,de+1,pt+p.second);
}
}
void dfs3(int x,int par,long long de,long long pt){
if(pt>k)return;
if(hm[pt]>de||hm[pt]==0)hm[pt]=de;
for(auto p:r2[x]){
if(p.first==par||vis[p.first])continue;
dfs3(p.first,x,de+1,pt+p.second);
}
}
int cent(int x,int par,int n){
for(auto p:r[x]){
if(p==par||vis[p])continue;
if(br[p]>n/2)return cent(p,x,n);
}
return x;
}
void decomp(int x){
hm.clear();
dfs(x,-1);
//cout<<br[x]<<" "<<x;
int y=cent(x,-1,br[x]);
vis[y]=1;
for(auto p:r2[y]){
if(vis[p.first])continue;
dfs2(p.first,-1,1,p.second);
dfs3(p.first,-1,1,p.second);
}
for(auto p:r[y]){
if(vis[p])continue;
decomp(p);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;
k=K;
for(int i=0;i<n-1;i++){
int x=H[i][0],y=H[i][1],z=L[i];
r[x].push_back(y);
r[y].push_back(x);
r2[x].push_back({y,z});
r2[y].push_back({x,z});
}
decomp(0);
if(fans==INT_MAX)return -1;
return fans;
}
