#include <bits/stdc++.h>
#include <race.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;
}
void dfs(int v, int p, map<ll, int> &S, int d, int dd){
S[d] = (S[d] == 0 ? dd : min(dd, S[d]));
for(Edge U: g[v]){
int u = U.to;
if(!vis[u] && u != p) dfs(u, v, S, min(d + U.e, INT_MAX/2), dd + 1);
}
}
void centroid(int v){
int C = centro(v, 0, pre(v, 0));
map<ll, int> s;
dfs(C, 0, s, 0, 0);
for(auto u: s){
if(u.first <= k)
if(s.find(k - u.first) != s.end()){
ans = min(ans, u.second + s[k - u.first]);
}
}
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);
}
