#include "race.h"
#include <stdio.h>
#include <stdlib.h>
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 500000
vector<int> grafo[200005],peso[200005];
long long k,n,siz[200005],ans;
long long lazy[200005],lazyval[200005];
map<long long,long long> sol[200005];
/*4 3
0 1 1
1 2 2
1 3 4
-----
11 19
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
void dfs(int nodo,int last){
//cout<<nodo<<" arrivo da "<<last<<endl;
siz[nodo]=1;
int best=0,num;
long long val=0;
for(int i=0;i<grafo[nodo].size();i++){
if(grafo[nodo][i]!=last){
//cout<<"chiamo "<<grafo[nodo][i]<<" "<<nodo<<" "<<last<<endl;
dfs(grafo[nodo][i],nodo);
siz[nodo]+=siz[grafo[nodo][i]];
if(siz[grafo[nodo][i]]>best){
swap(sol[nodo],sol[grafo[nodo][i]]);
lazy[nodo]--;
lazy[grafo[nodo][i]]++;
swap(lazy[nodo],lazy[grafo[nodo][i]]);
lazyval[nodo]-=peso[nodo][i];
lazyval[grafo[nodo][i]]+=peso[nodo][i];
swap(lazyval[nodo],lazyval[grafo[nodo][i]]);
best=siz[grafo[nodo][i]];
}
}
}
sol[nodo][0-lazyval[nodo]]=0-lazy[nodo];
for(int i=0;i<grafo[nodo].size();i++){
if(grafo[nodo][i]!=last){
for(auto j : sol[grafo[nodo][i]]){
num=j.second+lazy[grafo[nodo][i]]+1;
val=j.first+lazyval[grafo[nodo][i]]+peso[nodo][i];
if(sol[nodo].find(k-val-lazyval[nodo])!=sol[nodo].end())
ans=min(ans,num+sol[nodo][k-val-lazyval[nodo]]+lazy[nodo]);
}
for(auto j : sol[grafo[nodo][i]]){
num=j.second+lazy[grafo[nodo][i]]+1;
val=j.first+lazyval[grafo[nodo][i]]+peso[nodo][i];
//cout<<"dal figlio "<<grafo[nodo][i]<<" prendo "<<j.second+lazy[grafo[nodo][i]]<<"e "<<j.first+lazyval[grafo[nodo][i]]<<endl;
if(sol[nodo].find(val-lazyval[nodo])!=sol[nodo].end())
sol[nodo][val-lazyval[nodo]]=min(sol[nodo][val-lazyval[nodo]],num-lazy[nodo]);
else sol[nodo][val-lazyval[nodo]]=num-lazy[nodo];
}
}
}
if(sol[nodo].find(k-lazyval[nodo])!=sol[nodo].end())ans=min(ans,sol[nodo][k-lazyval[nodo]]+lazy[nodo]);
/*cout<<"info nodo "<<nodo<<":"<<endl;
for(auto i : sol[nodo]){
cout<<i.first+lazyval[nodo]<<" "<<i.second+lazy[nodo]<<endl;
}
cout<<"fine -----------"<<endl;*/
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;
k=K;
ans=10000000ll;
for(int i=0;i<n-1;i++){
grafo[H[i][0]].push_back(H[i][1]);
grafo[H[i][1]].push_back(H[i][0]);
peso[H[i][0]].push_back(L[i]);
peso[H[i][1]].push_back(L[i]);
}
dfs(0,-1);
if(ans==10000000ll)return -1;
return ans;
}
/*
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;
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));
}
int main()
{
int ans;
read_input();
ans = best_path(N,K,H,L);
cout<<ans<<endl;
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}*/
