//
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
int k;
vector<vector<pi>> adj;
vector<int> sz;
vector<bool> erased;
// vector<map<int, int>> children;
map<int, int> children;
int ans = INT_MAX;
void get_sz(int i, int p) {
sz[i] = 1;
for(auto [u, c] : adj[i]) {
if(u == p || erased[u]) continue;
get_sz(u, i);
sz[i] += sz[u];
}
}
int centroid(int i, int p, int n) {
for(auto [u, c] : adj[i]) {
if(u == p || erased[u]) continue;
if(sz[u] > n/2) return centroid(u, i, n);
}
return i;
}
void dfs(int i, int p, ll d, int steps, bool add) {
if(d > k) return;
if(add) {
auto it = children.find(d);
if(it == children.end()) children[d] = steps;
else it->second = min(it->second, steps);
} else {
auto it = children.find(k - d);
if(it != children.end()) ans = min(ans, steps + it->second);
}
for(auto [u, c] : adj[i]) {
if(u == p || erased[u]) continue;
dfs(u, i, d + c, steps + 1, add);
}
}
void decompose(int i) {
get_sz(i, i);
i = centroid(i, i, sz[i]);
children.clear();
children[0] = 0;
for(int add = 0 ; add < 2 ; add++) {
for(auto [u, c] : adj[i]) {
if(erased[u]) continue;
dfs(u, i, c, 1, false);
}
}
erased[i] = true;
for(auto [u, c] : adj[i]) {
if(!erased[u]) decompose(u);
}
}
int best_path(int n, int K, int edges[][2], int l[]) {
k = K;
adj.resize(n + 1);
for(int i = 0 ; i < n - 1 ; i++) {
int a = edges[i][0];
int b = edges[i][1];
int c = l[i];
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
sz.resize(n + 1);
erased.resize(n + 1);
decompose(1);
return ans;
}
// int main(void) {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// int t; cin >> t; while(t--) solve();
// return 0;
// }
