#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
vector<pair<int,ll>> g[200100];
int level[1001], dist[1001];
int k, ans = -1;
int minl[200100][110] = {0};
void dfs(int node, int prev = -1){
if(dist[node] == k){
ans = ans == -1 ? level[node] : min(ans, level[node]);
}
for(auto i : g[node]){
if(i.first != prev){
level[i.first] = level[node] + 1;
dist[i.first] = dist[node] + i.second;
dfs(i.first, node);
}
}
}
void dfs2(int node, int prev = -1){
for(auto i : g[node]){
if(i.first != prev){
dfs2(i.first, node);
vector<int> temp(k + 1);
if(i.second <= k)
temp[i.second] = 1;
for(int j = 1; j + i.second <= k; ++j){
if(minl[i.first][j] == 0) continue;
temp[j + i.second] = minl[i.first][j] + 1;
}
for(int j = 1; j < k; ++j){
if(temp[j] > 0 && minl[node][k - j] > 0){
if(ans == -1){
ans = temp[j] + minl[node][k - j];
}
else{
ans = min(ans, temp[j] + minl[node][k - j]);
}
}
}
if(temp[k] > 0){
ans = ans == -1 ? temp[k] : min(ans, temp[k]);
}
if(i.second <= k)
minl[node][i.second] = 1;
for(int j = 1; j + i.second <= k; ++j){
if(minl[i.first][j] == 0) continue;
if(minl[node][j + i.second] == 0){
minl[node][j + i.second] = minl[i.first][j] + 1;
}
else{
minl[node][j + i.second] = min(minl[i.first][j] + 1, minl[node][j + i.second]);
}
}
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for(int i = 0; i < N - 1; ++i){
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
if(N <= 1000){
for(int i = 0; i < N; ++i){
fill(level, level + N, 0);
fill(dist, dist + N, 0);
dfs(i);
}
}
else{
dfs2(0);
}
return ans;
}
