#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define mp make_pair
#define pb push_back
int n,k,res;
vector<pair<int,int> > adj[200001];
int sub[200001],lvl[200001],par[200001];
int ans[1000001];
stack<int> st;
int dfs1(int u,int p,int l){
sub[u]=1;
for (auto i:adj[u]){
if (lvl[i.first]!=-1) continue;
if (i.first==p) continue;
sub[u]+=dfs1(i.first,u,l);
}
return sub[u];
}
int dfs2(int u,int p,int sn){
for (auto i:adj[u]){
if (lvl[i.first]!=-1) continue;
if (i.first==p) continue;
if (sub[i.first]>sn/2){
return dfs2(i.first,u,sn);
}
}
return u;
}
vector<pair<int,int> > branch;
void dfs3(int u,int p,long long dist,int edges){
//cout<<dist<<" "<<edges<<'\n';
if (dist>k){
return;
}
branch.pb(mp(dist,edges));
st.push(dist);
for (auto i:adj[u]){
if (lvl[i.first]!=-1) continue;
if (i.first==p) continue;
dfs3(i.first,u,dist+i.second,edges+1);
if (p==-1){
branch.pb(mp(dist,edges));
for (auto j:branch){
res=min(res,ans[k-j.first]+j.second);
}
for (auto j:branch){
ans[j.first]=min(ans[j.first],j.second);
}
branch.clear();
}
}
}
// Building from node u, with a parent p and level l
void build(int u,int p,int l){
int cn=dfs1(u,p,l);
int cent=dfs2(u,p,cn);
if (p==-1) p=cent;
par[cent]=p;
lvl[cent]=l;
//cout<<"centroid: "<<cent<<'\n';
dfs3(cent,-1,0,0);
while (!st.empty()){
int cur=st.top();
ans[cur]=1e9;
st.pop();
}
for (auto i:adj[cent]){
if (lvl[i.first]!=-1) continue;
build(i.first,cent,l+1);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;
k=K;
for (int i=0;i<n-1;i++){
adj[H[i][0]].pb(mp(H[i][1],L[i]));
adj[H[i][1]].pb(mp(H[i][0],L[i]));
}
res=1e9;
for (int i=0;i<=k;i++) ans[i]=1e9;
memset(lvl,-1,sizeof(lvl));
build(0,-1,0);
if (res==1e9) return -1;
return res;
}
