#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
//const int MAX_N=2e5+14;
#define KK 1000001
int n,k;
int ans;
int mx_depth;
int cnt[KK];
bool removed[MAXN];
int subtree[MAXN];
vector<pair<int,int>>graph[MAXN];
int treesize(int node,int parent){
subtree[node]=1;
for(auto [w,child]:graph[node]){
if(child!=parent && !removed[child]){
subtree[node]+=treesize(child,node);
}
}
return subtree[node];
}
int findcentroid(int node,int parent,int treesz){
int sz=treesz/2;
for(auto[w,child]:graph[node]){
if(child!=parent && !removed[child]&& subtree[child]>(sz)){
return findcentroid(child,node,treesz);
}
}
return node;
}
void getans(int sum,int node,int parent,int depth,bool filling){
if (sum>k){
return;
}
// mx_depth=max(mx_depth,sum);
if(filling==true){
if(cnt[sum]==-1)cnt[sum]=depth;
else{
cnt[sum]=min(cnt[sum],depth);}
}
else{
if(cnt[k-sum]!=-1){
if(ans==-1){
ans=depth+cnt[k-sum];
}
ans=min(ans,depth+cnt[k-sum]);
}
}
for(auto[w,child]:graph[node]){
if(child!=parent && ! removed[child]){
getans(sum+w,child,node,depth+1,filling);
}
}
}
void del(int sum,int node,int p=-1){
if(sum>k)return;
cnt[sum]=-1;
for(auto[w,child]:graph[node]){
if(!removed[child]&& child!=p){
del(sum+w,child,node);
}
}
}
void centroid_decomp(int node,int parent){
int centroid=findcentroid( node, parent,treesize(node,parent));
removed[centroid]=true;
cnt[0]=0;
for(auto &[w,child]:graph[centroid]){
if(!removed[child]){
getans(w,child,centroid,1,false);
getans(w,child,centroid,1,true);
}
}
//fill(cnt+1,cnt+mx_depth+1,inf);
for(auto[w,i]:graph[centroid]){
if(!removed[i]){
del(w,i);
}
}
for(auto[w,i]:graph[centroid]){
if(!removed[i]){
centroid_decomp(i,centroid);}
}
}
int best_path(int N,int K,int H[][2],int L[]){
mx_depth=0;
n=N;
k=K;
// graph.resize(n);
for(int i=0;i<n-1;i++){
int u=H[i][0];
int v=H[i][1];
int w=L[i];
graph[u].push_back({w,v});
graph[v].push_back({w,u});
}
ans=-1;
memset(cnt,-1,sizeof(cnt));
// memset(removed,false,sizeof(removed));
centroid_decomp(0,0);
// if(ans>=inf)ans=-1;
return ans;
}
