#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 ll INF = 1e18;
const int N = 100005;
const int MAXM = 4200005;
const int LOG2 = 17;
const int inv = 1112;
const int MOD =998244353 ;
int dx[]= {0,0,-1,1};
int dy[] = {1 , - 1 , 0 , 0};
// Author : T_Danh - Tri An High School
vector<pii> adj[N];
int res = 1e9;
unordered_map<int,int> dfs(int u, int p, int k ) {
unordered_map<int,int> cur;
for(auto& [v , w] : adj[u]) if(v == p){
unordered_map<int,int> tmp = dfs(v , u, k);
if(cur.size() < tmp.size()) swap(cur , tmp);
for(auto& [val , d] : tmp){
int nval = val + w;
int nd = d + 1;
if(nval > k) continue;
if(nval == k) {
res = min(res , nd);
continue;
}
if(cur.find(k - nval) != cur.end()){
res = min(res , nd + cur[k - nval]);
}
}
for(auto& [val , d] : tmp){
int nval = val + w;
int nd = d + 1;
cur[nval] = min(cur[nval] , nd);
}
}
return cur;
}
int best_path(int n ,int k ,int H[][2],int L[] ) {
FOR(i,0,n-1){
adj[H[i][0]].eb(H[i][1] , L[i]);
adj[H[i][1]].eb(H[i][0] , L[i]);
}
dfs(1 , 1 , k);
return res;
}
// int main() {
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// #define NAME "runaway"
// if (fopen(NAME ".in", "r"))
// freopen(NAME ".in", "r", stdin),
// freopen(NAME ".out", "w", stdout);
// solve();
// return 0;
// }
