//
#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<ll, 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) {
// cout << "here " << d << " " << steps << endl;
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);
// cout << "inserted " << d << endl;
} else {
auto it = children.find(k - d);
// cout << "searching " << k-d << endl;
if(it != children.end()) ans = min(ans, steps + it->second);
// else cout << "not found " << k-d << endl;
}
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(auto [u, c] : adj[i]) {
if(erased[u]) continue;
dfs(u, i, c, 1, false);
dfs(u, i, c, 1, true);
}
erased[i] = true;
// cout << "cent " << i << endl;
// for(auto [d, s] : children) {
// cout << "\t " << d << " " << s << endl;
// }
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(0);
if(ans == INT_MAX) ans = -1;
return ans;
}
// int main(void) {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// // int n = 3;
// // int k = 3;
// // int edges[][2] = {
// // {0, 1},
// // {1, 2}
// // };
// // int l[] = {1, 1};
// int n = 4;
// int k = 3;
// int edges[][2] = {
// {0, 1},
// {1, 2},
// {1, 3}
// };
// int l[] = {1, 2, 4};
// cout << best_path(n, k, edges, l) << endl;
// return 0;
// }
