/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
//#include "race.h"
int n,k,ans=1e9,inf=1e9;
vector<vector<array<ll,2>>>a;
vector<int>sz,vis,d,dd;
int mn,mx,mmn,mmx,tot;
void gsz(int i,int p){
sz[i]=1;
for(auto&[j,w]:a[i]){
if(!vis[j]&&j!=p){gsz(j,i);sz[i]+=sz[j];}
}
}
int gc(int i,int p){
for(auto&[j,w]:a[i]){
if(!vis[j]&&j!=p&&sz[j]*2>tot)return gc(j,i);
}
return i;
}
void calc1(int i,int p,int dis,int dpt){
d[dis]=min(d[dis],dpt);
mn=min(mn,dis);
mx=max(mx,dis);
for(auto&[j,w]:a[i]){
if(!vis[j]&&j!=p&&dis+w<=k)calc1(j,i,dis+w,dpt+1);
}
}
void calc(int i){
gsz(i,-1);tot=sz[i];
int c=gc(i,-1);
vis[c]=1;
mmn=mmx=0;
d[0]=dd[0]=0;
for(auto&[j,w]:a[c]){
if(vis[j]||w>k)continue;
mn=mx=0;
d[0]=0;
calc1(j,c,w,1);
for(int l=mn;l<=mx;l++){
ans=min(ans,dd[k-l]+d[l]);
}
for(int l=mn;l<=mx;l++){dd[l]=min(dd[l],d[l]);d[l]=inf;}
}
ans=min(ans,dd[k]);
for(int l=mmx;l<=mmx;l++)dd[k]=inf;
for(auto&[j,w]:a[c]){
if(!vis[j])calc(j);
}
}
int best_path(int N,int K,int H[][2],int L[]){
n=N;k=K;a.resize(n);
for(int i=0;i+1<n;i++){
int u=H[i][0],v=H[i][1],w=L[i];
a[u].push_back({v,w});
a[v].push_back({u,w});
}
vis.assign(n,0);sz=vis;
d.assign(k+1,inf);dd=d;
calc(0);
return (ans==inf?-1:ans);
}
