#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector
#define int long long
vi<vi<pair<int,int>>> g;
vi<int> vis, sz, dis(1e6+5);
queue<int> rem;
const int inf = 1e18;
int ans=inf;
int dfs(int i, int par){
sz[i]=1;
for(auto &[x, val]:g[i]){
if(vis[x] || x==par)continue;
sz[i]+=dfs(x, i);
}
return sz[i];
}
int get_cent(int i, int par, int mx){
for(auto &[x, val]:g[i]){
if(vis[x] || x==par)continue;
if(sz[x]>mx/2)return get_cent(x, i, mx);
}
return i;
}
void search(int u, int par, int k, queue<pair<int,int>> &nw, int d, int w){
if(k<w)return;
ans=min(ans, dis[k-w]+d);
nw.push({d, w});
for(auto &[x, val]:g[u]){
if(vis[x] || x==par)continue;
search(x, u, k, nw, d+1, w+val);
}
}
void get_ans(int u, int p, int k){
int cent=get_cent(u, p, dfs(u, p));
queue<pair<int,int>> nw;
dis[0]=0;
for(auto &[x, val]:g[cent]){
if(vis[x])continue;
search(x, cent, k, nw, 1, val);
while(!nw.empty()){
auto [d, w] = nw.front();
nw.pop();
dis[w]=min(dis[w], d);
rem.push(w);
}
}
vis[cent]=1;
while(!rem.empty()){
int x=rem.front();
rem.pop();
dis[x]=inf;
}
for(auto [x, val]:g[cent]){
if(vis[x])continue;
get_ans(x, cent, k);
}
}
int32_t best_path(int32_t n, int32_t k, int32_t h[][2], int32_t l[]){
for(int i=0; i<=1e6; i++)dis[i]=inf;
g.assign(n, {});
vis.assign(n, 0);
sz.assign(n+1, 0);
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]});
}
get_ans(0, -1, k);
if(ans==inf)return -1;
else return ans;
}
