#include <bits/stdc++.h>
using namespace std;
// Usage: addEdge(u, v) - O(1)
// init() - O(n log)
// use cenRoot, cenChild, cenDad to get the relations in Centroid Tree
struct CentroidDecomposition {
int n, cenRoot;
vector<int> cenDad, subCD;
vector<vector<int>> cenChild, adj;
vector<set<int>> s;
// n vertices
CentroidDecomposition(int n): n(n) {
cenDad.resize(n + 1);
cenChild.resize(n + 1);
s.resize(n + 1);
subCD.resize(n + 1);
adj.resize(n + 1);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
int dfsCD(int a, int par) {
subCD[a] = 1;
for (int i: s[a]) {
if (i != par) {
dfsCD(i, a);
subCD[a] += subCD[i];
}
}
return subCD[a];
}
int centroid(int a, int p, int n) {
for (auto i: s[a]) {
if (i != p && subCD[i] > n / 2) {
return centroid(i, a, n);
}
}
return a;
}
void centroidDec(int a, int p) {
int n = dfsCD(a, p);
int cen = centroid(a, p, n);
cenDad[cen] = p;
if(p) cenChild[p].push_back(cen);
else cenRoot = cen;
for (int i:s[cen]){
s[i].erase(cen);
centroidDec(i,cen);
}
}
void init() {
for (int i = 1; i <= n; i++) {
for (auto j: adj[i]) s[i].insert(j);
}
dfsCD(1, 0);
centroidDec(1, 0);
}
};
set<array<int, 2>> adj[200005];
int s[200005], d[200005], minDist[1000005], res = 1e9;
void dfs(int u, int p) {
for (auto i: adj[u]) {
if (i[0] == p) continue;
d[i[0]] = d[u] + 1;
s[i[0]] = s[u] + i[1];
dfs(i[0], u);
}
}
vector<int> solve(int u, CentroidDecomposition& tree, int k) {
vector<vector<int>> childV;
vector<array<int, 2>> tmp;
for (auto [i, c]: adj[u]) {
tmp.push_back({i, c});
adj[i].erase(adj[i].lower_bound({u, 0}));
}
for (auto i: tree.cenChild[u]) {
childV.push_back(solve(i, tree, k));
}
for (auto [i, c]: tmp) {
adj[i].insert({u, c});
}
vector<int> v = {u};
d[u] = s[u] = 0;
dfs(u, 0);
minDist[0] = 0;
for (auto v1: childV) {
for (auto j: v1) {
if (s[j] > k) continue;
res = min(res, minDist[k - s[j]] + d[j]);
}
for (auto j: v1) {
if (s[j] <= k)
minDist[s[j]] = min(minDist[s[j]], d[j]);
v.push_back(j);
}
}
for (auto i: v) {
if (s[i] <= k) {
minDist[s[i]] = 1e9;
}
}
return v;
}
int best_path(int N, int K, int H[][2], int L[]) {
int n = N, k = K;
CentroidDecomposition tree(n);
for (int i = 0; i < n - 1; i++) {
int u = H[i][0], v = H[i][1], c = L[i];
// cin >> u >> v >> c;
u++; v++;
tree.addEdge(u, v);
adj[u].insert({v, c});
adj[v].insert({u, c});
}
tree.init();
for (int i = 0; i <= k; i++) {
minDist[i] = 1e9;
}
solve(tree.cenRoot, tree, k);
if (res > n) {
res = -1;
}
// cout << res << endl;
return res;
}
