#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<pair<int, int>> Ver[200005];
int naj[1000006];
bool kil[200005];
vector<int> czy;
int sz[200005];
int ans = 1e9 + 1;
int dfs_sz(int u, int v) {
sz[u] = 1;
for (auto &x : Ver[u]) {
if (x.first != v && !kil[x.first]) {
sz[u] += dfs_sz(x.first, u);
}
}
return sz[u];
}
void upd(int u, bool cz, int suma, int ile, int v) {
if (suma > k) return;
czy.emplace_back(suma);
if (cz) {
ans = min(ans, naj[k - suma] + ile);
} else {
naj[suma] = min(naj[suma], ile);
}
for (auto &x : Ver[u]) {
if (!kil[x.first] && x.first != v) {
upd(x.first, cz, suma + x.second, ile + 1, u);
}
}
}
int cent(int u, int v, int nk) {
for (auto &x : Ver[u]) {
if (x.first != v && !kil[x.first] && 2 * sz[x.first] > nk)
return cent(x.first, u, nk);
}
return u;
}
void centroid(int u) {
int root = cent(u, -1, dfs_sz(u, -1));
kil[root] = 1;
czy.clear();
for (auto &x : Ver[root]) {
if (!kil[x.first]) {
upd(x.first, 1, x.second, 1, root);
upd(x.first, 0, x.second, 1, root);
}
}
for (auto &x : czy) {
naj[x] = 1e9 + 2137;
}
for (auto &x : Ver[root]) {
if (!kil[x.first])
centroid(x.first);
}
}
int best_path(int N, int K, int V[][2], int len[]) {
n = N;
k = K;
for (int i = 0; i < n - 1; i++) {
Ver[V[i][0] + 1].push_back({V[i][1] + 1, len[i]});
Ver[V[i][1] + 1].push_back({V[i][0] + 1, len[i]});
}
fill(naj, naj + 1000006, 1e9 + 2137);
naj[0] = 0;
centroid(1);
return (ans == 1e9 + 1 ? -1 : ans);
}
