#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <map>
#include "race.h"
//#include <bits/stdc++.h>
#define in cin
#define out cout
#define mkp make_pair
using namespace std;
using ll = long long;
ifstream fin("test.in");
ll n, k, mini = -1;
vector<int> g[200001], d[200001];
int dim[200001]; // size (local calculat) (you'll see)
int dp[200001]; // dp[i] = dim max a unui subarb daca il elimin pe i (tot local) (you'll also see)
bool acc[200001];
void det_size(int nod, int f){
dim[nod] = 0;
for(int cop : g[nod]){
if(cop == f || !acc[cop]) continue;
det_size(cop, nod);
dim[nod] += dim[cop];
}
dim[nod]++;
}
void det_dp(int nod, int f, int size_subt){
dp[nod] = size_subt - dim[nod];
for(int cop : g[nod]){
if(cop == f || !acc[cop]) continue;
det_dp(cop, nod, size_subt);
dp[nod] = max(dp[nod], dim[cop]);
}
}
int centroidul(int nod, int f, int size_subt){
if(dp[nod] <= size_subt / 2) return nod;
for(int cop : g[nod]){
if(cop == f || !acc[cop]) continue;
int cc = centroidul(cop, nod, size_subt);
if(cc != -1) return cc;
}
return -1;
}
void mergeLeft(map< ll, int > & a, map< ll, int > & b, int add, int addL){
for(auto i : b){
if(i.first + add > k || (mini != -1 && i.second + addL > mini)) continue;
auto it = a.find(i.first + add);
if(it == a.end()) a[ i.first + add ] = i.second + addL;
else (*it).second = min((*it).second, i.second + addL);
}
}
void drumuri(int nod, int f, map<ll, int> & mp, int offset, int len){ // offset = cat e drumul de la root la mine
if(offset > k) return;
if(mini != -1 && len > mini) return;
if(mp.find(offset) != mp.end()) mp[offset] = min(mp[offset], len);
else mp[offset] = len;
// cout << "DRUMURI : Am ajuns la " << nod << " parintele " << f << " map (mp) offset = " << offset << " len = " << len << '\n';
int poz = 0;
for(int cop : g[nod]){
if(cop == f || !acc[cop]){ poz++; continue; }
drumuri(cop, nod, mp, offset + d[nod][poz], len + 1);
poz++;
}
}
void proc_arb(int nod){
// cout << "Procesam subarborele lui " << nod << '\n';
// cerr << "Start " << nod << '\n';
det_size(nod, -1); det_dp(nod, -1, dim[nod]);
int cen = centroidul(nod, -1, dim[nod]);
// cerr << "End preprocesare " << nod << '\n';
if(cen == -1) cen = nod;
// cout << " -- > dp : " << dp[1] << " size = " << dim[1] << '\n';
// cout << " -- > gasim centroidul ca " << cen << '\n';
acc[cen] = 0;
// gasim mapurile
int poz = 0;
// cerr << "Incepem det " << nod << '\n';
map<ll, int> general;
for(int cop : g[cen]){
if(!acc[cop]){ poz++; continue;}
map<ll, int> mp;
drumuri(cop, cen, mp, d[cen][poz], 1);
// cout << " -- > cop = " << cop << " mp = \n";
// for(auto i : mp){
// cout << " -- > " << i.first << " , " << i.second << '\n';
// }
for(auto i : mp){
// cout << " -- > pentru " << i.first << " , " << i.second << " am nevoie de suma " << k - i.first << '\n';
if(general.find( k - i.first ) == general.end()) continue;
int len = general[k - i.first ] + i.second;
// cout << " -- > Gasesc drum de lungime " << len << '\n';
if(mini == -1 || mini > len) mini = len;
}
mergeLeft(general, mp, 0, 0);
poz++;
}
// cerr << "Termin determinarea " << nod << '\n';
// cout << "In general : \n";
// for(auto i : general){
// cout << " -- > " << i.first << " , " << i.second << '\n';
// }
if( general.find(k) != general.end() && (mini == -1 || general[k] < mini) ) mini = general[k];
for(int cop : g[cen]){
if(!acc[cop]) continue;
proc_arb(cop);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N; k = K;
for(int i = 0; i < n; i++) acc[i] = 1;
// cerr << "Start\n";
for(int i = 0; i < N - 1; i++){
g[ H[i][0] ].push_back( H[i][1] );
g[ H[i][1] ].push_back( H[i][0] );
d[ H[i][0] ].push_back( L[i] );
d[ H[i][1] ].push_back( L[i] );
}
// cerr << "End\n";
proc_arb(0);
return mini;
}
// signed main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// int n, k; in >> n >> k;
// int H[n - 1][2], L[n - 1];
// for(int i = 0; i < n - 1; i++) in >> H[i][0] >> H[i][1] >> L[i];
// // for(int i = 0; i < n - 1; i++) in >> L[i];
// out << best_path(n, k, H, L) << '\n';
// return 0;
// }
