#include "race.h"
#include <bits/stdc++.h>
#define sc second
#define ff first/*
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 500000
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;*/
using namespace std;
typedef pair<int,int> ii;
/*inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(2==scanf("%d %d",&N,&K));
for(i=0; i<N-1; i++)
my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
my_assert(1==scanf("%d",&solution));
}*/
set<ii> G[200010];
int exist[1000010];
int sz[200010];
int edgecnt[1000010];
int tt;
int n,k;
int dfs(int node,int pad){
sz[node]=1;
for(auto i:G[node]){
if(i.ff==pad)continue;
sz[node]+=dfs(i.ff,node);
}
return sz[node];
}
int centroid(int node,int pad,int tam){
//cout<<node<<endl;
for(auto i:G[node]){
if(i.ff==pad)continue;
if(sz[i.ff]>tam/2)return centroid(i.ff,node,tam);
}
return node;
}
int dfs2(int node,int pad,int dis,int edge,int comp,vector<ii>& v){
//cout<<node<<endl;
int want=k-dis;
int ans=1e9;
if(want>=0 && exist[want]==comp){
ans=min(ans,edgecnt[want]+edge);
}
//cout<<k<<endl;
if(dis<=k){
v.push_back({dis,edge});
for(auto i:G[node]){
if(i.ff==pad)continue;
ans=min(ans,dfs2(i.ff,node,dis+i.sc,edge+1,comp,v));
}
}
return ans;
}
int solve(int node,int pad){
int subsz=dfs(node,pad);
int piv=centroid(node,pad,subsz);
//cout<<123<<endl;
int ans=1e9;
int ac=++tt;
exist[0]=ac;edgecnt[0]=0;
for(auto i:G[piv]){
vector<ii> tmp;
ans=min(ans,dfs2(i.ff,piv,i.sc,1,ac,tmp));
//cout<<ans<<" "<<ac<<endl;
for(auto j:tmp){
if(exist[j.ff]!=ac || (exist[j.ff]==ac && edgecnt[j.ff]>j.sc)){
exist[j.ff]=ac;
edgecnt[j.ff]=j.sc;
}
}
}
vector<ii> tmp (G[piv].begin(),G[piv].end());
for(auto i:tmp){
G[i.ff].erase(ii(piv,i.sc));
G[piv].erase(i);
ans=min(ans,solve(i.ff,piv));
//cout<<ans<<" "<<ac<<endl;
}
// cout<<ans<<" "<<ac<<endl;
return ans;
}
int best_path(int N, int K, int H[][2], int L[])
{
tt=0;
k=K;
memset(exist,0,sizeof exist);
for(int i=0;i<N-1;i++){
int a=H[i][0];
int b=H[i][1];
G[a].insert(ii(b,L[i]));
G[b].insert(ii(a,L[i]));
}
//cout<<123<<endl;
int h=solve(1,0);
if(h==1e9)return -1;
return h;
}/*
int main()
{
int ans;
read_input();
ans = best_path(N,K,H,L);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}
*/
