#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 2e5+10;
vector<pii> tree[mxn];
int dp[mxn*10];
int sz[mxn];
int dep[mxn];
int len[mxn];
bool del[mxn];
int K,N;
int ans = mxn*10;
void dfs1(int now,int par){
sz[now] = 1;
for(auto [nxt,w]:tree[now]){
if(nxt == par || del[nxt])continue;
dfs1(nxt,now);
sz[now] += sz[nxt];
}
return;
}
int find_centroid(int now,int par,int tar){
for(auto [nxt,w]:tree[now]){
if(nxt == par||del[nxt])continue;
if(sz[nxt]>tar)return find_centroid(nxt,now,tar);
}
return now;
}
void dfs2(int now,int par){
if(len[now]<mxn*10)dp[len[now]] = min(dp[len[now]],dep[now]);
if(K>=len[now])ans = min(ans,dep[now]+dp[K-len[now]]+1);
for(auto [nxt,w]:tree[now]){
if(nxt == par||del[nxt])continue;
dep[nxt] = dep[now]+1;
len[nxt] = len[now]+w;
dfs2(nxt,now);
}
return;
}
void dfs3(int now,int par){
if(len[now]<mxn*10)dp[len[now]] = mxn*10;
for(auto [nxt,w]:tree[now]){
if(nxt == par||del[nxt])continue;
dfs3(nxt,now);
}
return;
}
void cd(int now){
dfs1(now,now);
now = find_centroid(now,now,(sz[now]-1)>>1);
dp[0] = 1;
for(auto [nxt,w]:tree[now]){
if(del[nxt])continue;
dep[nxt] = 1;
len[nxt] = w;
dfs2(nxt,now);
}
del[now] = 1;
for(auto [nxt,w]:tree[now]){
if(del[nxt])continue;
dfs3(nxt,now);
}
for(auto [nxt,w]:tree[now]){
if(!del[nxt])cd(nxt);
}
return;
}
int best_path(int n, int k, int H[][2], int L[]){
N = n,K = k;
fill(dp,dp+mxn*10,mxn*10);
for(int i = 0;i+1<N;i++){
int a = H[i][0],b = H[i][1],c = L[i];
tree[a].push_back(pii(b,c));
tree[b].push_back(pii(a,c));
}
cd(0);
return (ans>N?-1:ans-1);
}
