#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define ii pair<int,long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod=1e9+7;
const int M=1e6+10;
const int N=2e5+10;
int n,k;
vector<ii> ke[N];
bool dd[N];
int sz[N];
int child(int u,int p=0)
{
sz[u]=1;
for(auto [v,w]:ke[u]) if(v!=p&&!dd[v]) sz[u]+=child(v,u);
return sz[u];
}
int centroid(int u,int p=0)
{
for(auto [v,w]:ke[u]) if(v!=p&&!dd[v]&&sz[v]>n/2) return centroid(v,u);
return u;
}
int mi[M],kq=1e9;
vector<int> wdel;
void dfs(int u,int tt,int val,int depth,int p=0)
{
if(val>k) return ;
if(!tt) {
kq=min(kq,depth+mi[k-val]);
}
else {
if(mi[val]==1e9) wdel.pb(val);
mi[val]=min(mi[val],depth);
}
for(auto [v,w] :ke[u]) if(v!=p&&!dd[v]) dfs(v,tt,val+w,depth+1,u);
}
void solve(int u)
{
n=child(u);
int root=centroid(u);
dd[root]=true;
for(auto [v,w] : ke[root]) {
if(!dd[v]) {
dfs(v,0,w,1);
dfs(v,1,w,1);
}
}
for(int v: wdel) mi[v]=1e9;
wdel.clear();
for(auto [v,w] :ke[root]){
if(!dd[v]) solve(v);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for(int i = 0;i <= n - 2; i++) {
H[i][0]++;
H[i][1]++;
ke[H[i][0]].pb({H[i][1],L[i]});
ke[H[i][1]].pb({H[i][0],L[i]});
}
fori(i,1,1e6) mi[i]=1e9;
mi[0]=0;
solve(1);
return (kq==1e9 ? -1 : kq) ;
}
//int32_t main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// #define task "1"
// if(fopen(task".inp","r"))
// {
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
// cin >> n >> k;
// fori(i,1,n-1)
// {
// int u,v,w;
// cin >> u >> v >> w;
// u++;
// v++;
// ke[u].pb({v,w});
// ke[v].pb({u,w});
// }
// fori(i,1,1e6) mi[i]=1e9;
// mi[0]=0;
// solve(1);
// cout << (kq==1e9 ? -1 : kq) ;
//}
