#ifndef LOCAL
#include <bits/stdc++.h>
#define debug(...)
#endif
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5, H = 18, INF = 1e9;
int arr[N], sub[N], cth[N], ctp[N], mn[M], ans = INF, n, k;
vector<pair<int, int> > g[N];
void dfs_siz(int u, int p) {
sub[u] = 1;
for (auto &[v,w]: g[u]) if (!cth[v] && v ^ p) dfs_siz(v, u), sub[u] += sub[v];
}
int fc(int u, int p, int lim) {
for (auto &[v,w]: g[u]) if (!cth[v] && v ^ p && sub[v] > lim) return fc(v, u, lim);
return u;
}
void dfs_calc(int u, int p, int len, int d, int mark) {
if (len > k) return;
if (mark == 0) {
int need = k - len;
ans = min(ans, d + mn[need]);
}
else if (mark == 1) mn[len] = min(mn[len], d);
else mn[len] = INF;
for (auto [v,w]: g[u]) if (!cth[v] && p ^ v) dfs_calc(v, u, len + w, d + 1, mark);
}
void decompose(int u, int p, int h) {
dfs_siz(u, 0);
u = fc(u, 0, sub[u] >> 1);
cth[u] = h, ctp[u] = p;
mn[0]=0;
for (auto &[v,w]: g[u])
if (!cth[v]) {
dfs_calc(v, u, w, 1, false);
dfs_calc(v, u, w, 1, true);
}
for (auto &[v,w]: g[u]) if (!cth[v]) dfs_calc(v, u, w, 1, 2);
for (auto &[v,w]: g[u]) if (!cth[v]) decompose(v, u, h + 1);
}
int best_path(int _n, int _k, int H[][2], int L[]) {
n = _n, k = _k;
fill_n(mn, M, INF);
for (int i = 0; i < n - 1; ++i) {
int u = H[i][0], v = H[i][1], w = L[i];
u++, v++;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
decompose(1, 0, 1);
return ans == INF ? -1 : ans;
}
