#include "race.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> m, v[200005];
int g[200005],used[200005],n,k;
map<int ,int>len;
void dfs(int vi,int p){
g[vi]++;
for(int i=0;i<v[vi].size();i++){
int b=v[vi][i].first;
if(used[b]||b==p)continue;
dfs(b,vi);
g[vi]+=g[b];
}
}
int centr(int u,int p,int s){
for(auto x:v[u]){
int b=x.first;
if(used[b]||p==b)
continue;
if(g[b]>s/2)
return centr(b,u,s);
}
return u;
}
void dfs1(int vi,int p,int d,int t){
if(d>k)
return ;
m.push_back({d,t});
for(auto x:v[vi]){
int b=x.first;
int c=x.second;
if(used[b]||p) continue;
dfs1(b,vi,c+d,t+1);
}
}
void dfs2(int vi,int p,int d,int t){
if(d>k)
return ;
if(!len.count(d))
len[d]=t;
else
len[d]=min(t,len[d]);
m.push_back({d,t});
for(auto x:v[vi]){
int b=x.first;
int c=x.second;
if(used[b]||p) continue;
dfs2(b,vi,c+d,t+1);
}
}
int fans(int u,int p){
int ans=INT_MAX;
len.clear();
dfs(u,u);
//cout<<"works\n";
u=centr(u,u,g[u]);
len[0]=0;
used[u]=1;
//cout<<"works\n";
for(auto x:v[u]){
m.clear();
int b=x.first,c=x.second;
if(used[b]) continue;
dfs1(b,u,c,1);
for(auto x:m){
int d=x.first;
int t=x.second;;
if(len.count(k-d)){
ans=min(ans,len[k-d]+t);
}//cout<<d<<" "<<t<<"\n";
}
dfs2(b,u,c,1);
}
for( auto x : v[u]){
int b=x.first;
if(used[b]||p==b) continue;
ans=min(ans,fans(b,u));
}
return ans;
}
int best_path(int N, int K, int h[][2], int l[]){
n=N,k=K;
if(k==0)
return 0;
for(int i=0;i<n-1;i++){
v[h[i][0]].push_back({h[i][1],l[i]});
v[h[i][1]].push_back({h[i][0],l[i]});
}
int ans=fans(0,-1);
ans=(ans==INT_MAX ? -1:ans);
cout<<ans<<" ";
return ans;
}
/*
4 3
0 1 1
1 2 2
1 3 4
2
*/
