#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n,k,inf=1e7,ans=inf,sz[200005],cnt[1000006];bool vis[200005];
vector<pair<int,int>>v[200005],part;//part: first=dist,second=highways
vector<int>all;
void dfssz(int nod,int par){
sz[nod]=1;
for(auto i:v[nod]){
int u=i.first;
if(vis[u]||u==par)continue;
dfssz(u,nod);
sz[nod]+=sz[u];
}
}
int getcn(int nod,int par,int tot){
for(auto i:v[nod]){
int u=i.first;
if(u==par||vis[u])continue;
if(sz[u]>tot/2)return getcn(u,nod,tot);
}
return nod;
}
void dfs(int nod,int par,int d,int hw){
if(d>k)return;
part.pb({d,hw});
all.pb(d);
ans=min(ans,cnt[k-d]+hw);
for(auto i:v[nod]){
if(vis[i.first]||i.first==par)continue;
dfs(i.first,nod,d+i.second,hw+1);
}
}
void solve(int cn){
all.clear();
for(auto i:v[cn]){
int u=i.first;
if(vis[u])continue;
part.clear();
dfs(u,cn,i.second,1);
for(auto j:part){
cnt[j.first]=min(cnt[j.first],j.second);
}
}
for(auto i:all){
cnt[i]=inf;
}
}
void dec(int rot){
dfssz(rot,0);
int cn=getcn(rot,0,sz[rot]);
cnt[0]=0;
solve(cn);
vis[cn]=1;
for(auto i:v[cn]){
int u=i.first;
if(vis[u])continue;
dec(u);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N,k=K;
for(int i=0;i<n-1;i++){
int a=H[i][0],b=H[i][1],c=L[i];
v[a].pb({b,c});
v[b].pb({a,c});
}
for(int i=0;i<=k;i++){
cnt[i]=inf;
}
dec(1);
if(ans==inf)return -1;
return ans;
}
/*int N,K,L[200006],H[200006][2];
int main(){
cin>>N>>K;
for(int i=0;i<N-1;i++){
cin>>H[i][0]>>H[i][1]>>L[i];
}
int sol;
cin>>sol;
int x=best_path(N,K,H,L);
if(x==sol)cout<<"Correct"<<endl;
return 0;
}
*/
