#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(v) (v).begin(), (v).end()
const ll oo = 1e17;
const int mod = 1e9+7; // 998244353;
const int maxn = 2e5;
vector<pair<ll, ll>> adj[maxn+1];
bool bad[maxn+1];
int subtree_size[maxn+1];
ll k, ans;
void dfs_ssz(int v, int p){
subtree_size[v]=1;
for(auto [c, w]: adj[v]){
if(c^p and !bad[c]){
dfs_ssz(c, v);
subtree_size[v]+=subtree_size[c];
}
}
}
int find_centroid(int v, int p, int sz){
for(auto [c, w]: adj[v]){
if(!bad[c] and c^p and subtree_size[c]*2>sz)
return find_centroid(c, v, sz);
}
return v;
}
void calc(int v, int p, ll depth, ll weight, map<ll,ll>& mp, bool update){
if(update){
if(mp.count(weight)){
mp[weight] = min(mp[weight], depth);
}
else{
mp[weight] = depth;
}
}
else{
ll temp = k-weight;
if(mp.count(temp)){
ans = min(ans, depth+mp[temp]+1);
}
}
for(auto [c, w]: adj[v]){
if(!bad[c] and c^p){
calc(c, v, depth+1, weight+w, mp, update);
}
}
}
void decompose(int v, int p){
dfs_ssz(v, p);
int cen = find_centroid(v, p, subtree_size[v]);
bad[cen]=1;
map<ll, ll> mp;
mp[0] = 0;
for(auto [c, w]: adj[cen]){
if(!bad[c]){
calc(c, cen,1, w, mp,false);
calc(c, cen,1, w, mp,true);
}
}
for(auto [c, w]: adj[cen]){
if(!bad[c]){
decompose(c, cen);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
k = K, ans = INT_MAX;
for(int i = 0; i < N-1; i++){
adj[H[i][0]+1].push_back({H[i][1]+1, L[i]});
adj[H[i][1]+1].push_back({H[i][0]+1, L[i]});
}
decompose(1, 0);
if(ans==INT_MAX)
return -1;
return ans;
}
