#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1e6;
#define pb push_back
struct Edge{
int to, e;
};
int n, k, ans, s[M];
vector<Edge> g[M];
vector<bool> vis;
int pre(int v, int p){
s[v] = 1;
for(Edge U: g[v]){
int u = U.to;
if(!vis[u] && u != p) pre(u, v), s[v] += s[u];
}
return s[v];
}
int centro(int v, int p, int sz){
for(Edge U: g[v]){
int u = U.to;
if(u != p && !vis[u] && s[u] * 2 > sz)
return centro(u, v, sz);
}
return v;
}
vector<pair<int, int>> ddd;
void dfs(int v, int p, map<int, int> &S, int d, int dd){
ddd.pb({d, dd});
if(d == k){
ans = min(ans, dd);
}
if(d <= k && S.find(k - d) != S.end())
ans = min(ans, dd + S[k - d]);
for(Edge U: g[v]){
int u = U.to;
if(!vis[u] && u != p)
dfs(u, v, S, min(d + U.e, 1000000000), dd + 1);
}
}
void centroid(int v){
int C = centro(v, 0, pre(v, 0));
map<int, int> s;
for(Edge U: g[C]){
int u = U.to;
if(!vis[u]){
ddd.clear();
dfs(u, C, s, U.e, 1);
for(auto v: ddd) s[v.first] = s[v.first] == 0 ? v.second : min(s[v.first], v.second);
}
}
vis[C] = 1;
for(Edge U: g[C]){
int u = U.to;
if(!vis[u])
centroid(u);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K, ans = N + 1;
for(int i = 0; i < n - 1; ++i){
g[H[i][0] + 1].pb({H[i][1] + 1, L[i]});
g[H[i][1] + 1].pb({H[i][0] + 1, L[i]});
}
vis.resize(n + 1);
centroid(1);
return (ans == N + 1 ? -1 : ans);
}
