#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ALL(A) A.begin(), A.end()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOR2(i, l, r) for (int i = l; i >= r; i--)
#define ce cout<<endl;
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using str = string;
using T = pair<ll,int>;
const int INF = 1e9;
const int N = 1e5;
const int K = 1e6;
const int MAXM = 4200005;
const int LOG2 = 17;
const int inv = 1112;
const int MOD =998244353 ;
const int LIM = 2 * N + 5;
int dx[]= {0,0,-1,1};
int dy[] = {1 , - 1 , 0 , 0};
// Author : T_Danh - Tri An High School
int n , k;
bool removed[N + 1];
vector<pii> adj[N + 1];
int sz[N + 1];
int best[K + 1];
int res = 1e9;
vector<pii> nodes;
void dfs_sz(int u, int p) {
sz[u] = 1;
for (auto& [v, w] : adj[u]) {
if (v != p && !removed[v]) {
dfs_sz(v, u);
sz[u] += sz[v];
}
}
}
int find_centroid(int u, int p, int subtree_sz) {
for (auto& [v, w] : adj[u]) {
if (v != p && !removed[v]) {
if (sz[v] > subtree_sz / 2) return find_centroid(v, u, subtree_sz);
}
}
return u;
}
void dfs_collect(int u, int p, int cur ,int cur_h) {
if(cur > K) return;
nodes.eb(cur, cur_h);
for (auto& [v, w] : adj[u]) if (v != p && !removed[v]) {
dfs_collect(v, u, cur + w, cur_h + 1);
}
}
void build(int node = 1) {
dfs_sz(node, -1);
int centroid = find_centroid(node, -1, sz[node]);
removed[centroid] = true;
best[0] ++;
vector<int> trace;
trace.eb(0);
for(auto& [v , w]: adj[centroid]) if(!removed[v]){
nodes.clear();
dfs_collect(v, centroid , w , 1);
for(auto& [dist , h] : nodes){
if(k >= dist)
res = min(res , best[k - dist] + h);
}
for(auto& [dist , h] : nodes){
best[dist] = min(best[dist] , h);
trace.eb(dist);
}
}
for(int i : trace) best[i] = 1e9;
for (auto& [v, w] : adj[centroid]) {
if (!removed[v]) build(v);
}
}
int best_path(int _n , int _k ,int H[][2] ,int L[] ) {
n = _n;
k =_k;
FOR(i, 0, n - 2) {
adj[H[i][0]].eb(H[i][1], L[i]);
adj[H[i][1]].eb(H[i][0], L[i]);
}
FOR(i,1,K) best[i] = 1e9;
build();
if(res == 1e9) return -1;
return res;
}
// int main() {
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// #define NAME "yinyang"
// if (fopen(NAME ".in", "r"))
// freopen(NAME ".in", "r", stdin),
// freopen(NAME ".out", "w", stdout);
// solve();
// return 0;
// }
