#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define all(v) v.begin(),v.end()
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define mk make_pair
typedef pair<int,int> pii;
const int maxn =2e5 + 10,maxv = 1e6 + 10,inf = 1e8 ;
int k;
int s[maxn],dp[maxv];
stack<int> st;
bool c[maxn];
int ans = inf;
vector<pii> adj[maxn];
void prep(int i,int p)
{
s[i] = 1;
for(auto [k,w] : adj[i])
{
if(k==p||c[k])continue;
prep(k,i);
s[i] += s[k];
}
}
int fi(int i,int p,int sz)
{
for(auto [k,w] : adj[i])
{
if(k==p||c[k])continue;
if(s[k] * 2 >= sz)return fi(k,i,sz);
}
return i;
}
void cal(int i,int p,int tmp,int cnt)
{
if(tmp>k)return;
ans = min(ans,cnt + dp[k - tmp]);
for(auto [k,w] : adj[i])
{
if(k==p||c[k])continue;
cal(k,i,tmp+w,cnt+1);
}
}
void fill(int i,int p,int tmp,int cnt)
{
if(tmp > k)return;
dp[tmp] = min(dp[tmp],cnt);
st.push(tmp);
for(auto [k,w] : adj[i])
{
if(k==p||c[k])continue;
fill(k,i,tmp+w,cnt+1);
}
}
void decompose(int i)
{
prep(i,0);
int cen = fi(i,0,s[i]);
c[cen] = 1;
// cout<<cen<<'\n';
//
for(auto [k,w] : adj[cen])
{
if(!c[k])
{
cal(k,0,w,1);
fill(k,0,w,1);
// cout<<k<<'\n';
}
}
for(;st.size();st.pop())if(st.top())dp[st.top()] = inf;
for(auto [k,w] : adj[cen])
{
if(!c[k])decompose(k);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for(int i = 1;i<maxv;i++)
{
dp[i] = inf;
}
for(int i = 0;i<N-1;i++)
{
H[i][0] ++;
H[i][1] ++;
adj[H[i][0]].pb(mk(H[i][1],L[i]));
adj[H[i][1]].pb(mk(H[i][0],L[i]));
// cout<<H[i][0]<<' '<<H[i][1]<<' '<<L[i]<<'\n';
}
decompose(1);
if(ans==inf)ans=-1;
return ans;
}
