#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
int n, k, inf=maxn*2, sh=maxn*2, v=-1, timer=1, l[maxn];
bool used[maxn];
pair<int, int> k1[1000005];
vector<pair<int, int>> g[maxn];
int dfs1(int u, int p, int n){
int sh=1;
for(auto i:g[u]){
if(i.f!=p&&!used[i.f]){
sh+=dfs1(i.f, u, n);
}
}
if(sh>n/2&&v==-1){
v=u;
}
return sh;
}
void dfs2(int u, int p, int ck, int cnt){
if(k1[k-ck].s==timer){
sh=min(sh, (k1[k-ck].f+cnt));
}
for(auto i:g[u]){
if(i.f!=p&&l[i.s]+ck<=k&&!used[i.f]){
dfs2(i.f, u, l[i.s]+ck, cnt+1);
}
}
}
int dfs3(int u, int p){
int sh=1;
for(auto i:g[u]){
if(!used[i.f]&&p!=i.f){
sh+=dfs3(i.f, u);
}
}
return sh;
}
void dfs4(int u, int p, int ck, int cnt){
for(auto i:g[u]){
if(i.f!=p&&l[i.s]+ck<=k&&!used[i.f]){
dfs4(i.f, u, l[i.s]+ck, cnt+1);
}
}
if(k1[ck].s<timer){
k1[ck]={cnt, timer};
}else{
k1[ck].f=min(k1[ck].f, cnt);
}
}
void rem(int u, int n){
v=-1;
if(n==1)return;
dfs1(u, u, n);
if(v==-1){
cout << 1/0;
}
k1[0]={0, timer};
for(auto i:g[v]){
if(!used[i.f]&&l[i.s]<=k){
dfs2(i.f, v, l[i.s], 1);
dfs4(i.f, v, l[i.s], 1);
}
}
used[v]=1;
timer++;
for(auto i:g[v]){
if(!used[i.f]){
rem(i.f, dfs3(i.f, v));
}
}
}
int best_path(int n1, int k1, int h[][2], int l1[]){
n=n1, k=k1;
for(int i=0; i<n-1; i++){
g[h[i][0]].push_back({h[i][1], i});
g[h[i][1]].push_back({h[i][0], i});
l[i]=l1[i];
}
rem(0, n);
return (sh==inf?-1:sh);
}
