#include <bits/stdc++.h>
#define ve vector
#define ar array
#define pb push_back
#define ins insert
#define endl '\n'
#define ll long long
using namespace std;
const int MXN = 2e5+5;
int K;
ve<pair<int, ll>> adj[MXN];
int dfs1(int x, int p, int need){
if(need == 0){
return 1;
}
if(need < 0){
return 1e9;
}
int ans = 1e9;
for(auto [i, c] : adj[x]){
if(i != p){
ans = min(ans, 1 + dfs1(i, x, need-c));
}
}
return ans;
}
int dfs2(int x, int p){
int ans = 1e9;
for(auto [i, c] : adj[x]){
if(i != p){
ans = min(ans, dfs1(i, x, K-c));
}
}
return ans;
}
map<int, int> pos[MXN];
int dfs3(int x, int p){
int ans = 1e8;
pos[x][0] = 0;
for(auto [i, c] : adj[x]){
if(i != p){
if(c > K){
continue;
}
ans = min(ans, dfs3(i, x));
for(int j = c; j <= K; j++){
if(pos[i].count(j-c) && pos[x].count(K-j)){
ans = min(ans, pos[i][j-c] + pos[x][K-j] + 1);
}
}
for(int j = 0; j+c <= K; j++){
if(pos[i].count(j)){
if(pos[x].count(j+c)){
pos[x][j+c] = min(pos[x][j+c], pos[i][j] + 1);
}
else{
pos[x][j+c] = pos[i][j] + 1;
}
pos[i].erase(j);
}
}
}
}
return ans;
}
int best_path(int N, int k, int H[][2], int L[]){
K = k;
for(int i = 0; i < N-1; i++){
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
if(K == 0){
return 0;
}
if(N <= 1000){
int ans = 1e9;
for(int i = 0; i < N; i++){
ans = min(ans, dfs2(i, -1));
}
if(ans == 1e9){
return -1;
}
else{
return ans;
}
}
else if(K <= 100){
int ans = dfs3(0, -1);
if(ans == 1e8){
ans = -1;
}
return ans;
}
}
