#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
const int inf = 1e9;
int d[N], dp[N], up[N][18];
int tin[N], tout[N], timer;
vector<array<int, 2>> g[N];
vector<vector<int>> dp100(N, vector<int> (101, inf));
int n, k, res = inf;
void dfs(int v, int p = 0) {
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i < 18; ++i)
up[v][i] = up[up[v][i - 1]][i - 1];
for (auto [to, w] : g[v]) {
if (to != p) {
d[to] = d[v] + 1;
dp[to] = dp[v] + w;
dfs(to, v);
}
}
tout[v] = ++timer;
}
bool upper(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
if (upper(u, v)) return u;
if (upper(v, u)) return v;
for (int i = 17; i >= 0; --i)
if (!upper(up[u][i], v))
u = up[u][i];
return up[u][0];
}
int get(int u, int v) {
int p = lca(u, v);
if (dp[u] + dp[v] - 2 * dp[p] == k)
return d[u] + d[v] - 2 * d[p];
return inf;
}
void dfs100(int v, int p) {
dp100[v][0] = 0;
for (auto [to, w] : g[v]) {
if (to != p) {
dfs100(to, v);
for (int i = 0; i + w <= k; ++i)
res = min(res, dp100[to][i] + dp100[v][k - i - w] + 1);
for (int i = 0; i + w <= k; ++i)
dp100[v][i + w] = min(dp100[v][i + w], dp100[to][i] + 1);
}
}
res = min(res, dp100[v][k]);
}
int best_path(int N, int K, int h[][2], int l[]) {
n = N, k = K;
for (int i = 0; i < n - 1; ++i) {
g[h[i][0]].push_back({h[i][1], l[i]});
g[h[i][1]].push_back({h[i][0], l[i]});
}
if (n <= 1000) {
dfs(0);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
res = min(res, get(i, j));
} else {
dfs100(0, -1);
}
return res < inf ? res : -1;
}
