#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
#define mod 1000000007
#define maxn 200005
int N,K,ans=INF,sub[maxn],dis[maxn],num[maxn],mn[1000005];
bool mark[maxn];
vi nodes[maxn];
vii AL[maxn];
void dfs(int u,int p){
sub[u]=1;
for(auto[v,w]:AL[u]){
if(mark[v]||v==p)continue;
dfs(v,u);
sub[u]+=sub[v];
}
}
void dfs2(int u,int p,int s){
if(s!=-1)nodes[s].pb(u);
for(auto[v,w]:AL[u]){
if(mark[v]||v==p)continue;
dis[v]=dis[u]+w;
if(dis[v]>=INF)dis[v]=INF;
num[v]=num[u]+1;
if(s==-1){
nodes[v].clear();
dfs2(v,u,v);
}
else dfs2(v,u,s);
}
}
void decomp(int u){
sub[u]=0;
dfs(u,-1);
int c=u;
while(true){
bool val=true;
for(auto[v,w]:AL[c]){
if(!mark[v]&&sub[v]<sub[c]&&sub[v]>sub[u]/2){
val=false;
c=v;break;
}
}
if(val)break;
}
dis[c]=0;num[c]=0;
dfs2(c,-1,-1);
for(auto[v,w]:AL[c]){
if(mark[v])continue;
for(int i:nodes[v]){
if(dis[i]>K)continue;
ans=min(ans,mn[K-dis[i]]+num[i]);
}
for(int i:nodes[v]){
if(dis[i]>K)continue;
mn[dis[i]]=min(mn[dis[i]],num[i]);
}
}
ans=min(ans,mn[K]);
for(auto[v,w]:AL[c]){
for(int i:nodes[v]){
if(dis[i]>K)continue;
mn[dis[i]]=INF;
}
}
mark[c]=true;
for(auto[v,w]:AL[c]){
if(!mark[v])decomp(v);
}
}
int best_path(int _N,int _K,int H[][2],int L[]){
N=_N;K=_K;
for(int i=0;i<=1000000;++i)mn[i]=INF;
for(int i=0;i<N-1;++i){
AL[H[i][0]].pb({H[i][1],L[i]});
AL[H[i][1]].pb({H[i][0],L[i]});
}
decomp(0);
return (ans!=INF)?ans:-1;
}
