#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
using namespace std;
struct node{
int lant, offsetS, offsetL;
map<int, int> mp; // mp[suma] = lungime minima
};
int n, k, mini = -1;
vector<int> g[200001], d[200001];
node v[200001];
void solutie(int nod, int f){ // rezolv subarb lui nod
v[nod].mp.clear();
int greu = -1;
v[nod].lant = 0;
int poz = 0;
for(int cop : g[nod]){
if(cop == f){ poz++; continue;}
solutie(cop, nod);
if(greu == -1 || v[cop].lant + 1 > v[nod].lant){
v[nod].lant = v[cop].lant + 1;
v[nod].offsetS = d[nod][poz] + v[cop].offsetS;
v[nod].offsetL = v[cop].offsetL + 1;
greu = cop;
}
poz++;
}
// cout << " -- > copil greu este " << greu << " pentru nodul " << nod << " la tatal " << f << '\n';
if(greu == -1){
v[nod].lant = 1;
v[nod].mp[0] = 0;
v[nod].offsetS = 0;
v[nod].offsetL = 0;
return;
}
v[nod].mp = v[greu].mp;
// cout << "Calculez la " << nod << " f = " << f << '\n';
poz = 0;
for(int cop : g[nod]){
if(cop == f || cop == greu){
// delete( &v[cop].mp );
// delete( &v[cop].mp ); //.clear();
v[cop].mp.clear();
poz++;
continue;
}
// cout << " -- > Copilul " << cop << " genereaza mp :\n";
// for(auto i : v[cop].mp){
// cout << " -- > " << i.first << " , " << i.second << '\n';
// }
for(auto i : v[cop].mp){
if( v[nod].mp.find( k - (i.first + v[cop].offsetS) - d[nod][poz] - v[nod].offsetS ) == v[nod].mp.end() ) continue;
int len = v[nod].mp[ k - (i.first + v[cop].offsetS) - d[nod][poz] - v[nod].offsetS ] + v[nod].offsetL + v[cop].offsetL + i.second + 1;
if(mini == -1 || mini > len) mini = len;
}
for(auto i : v[cop].mp){
// cout << " -- > facem suma " << i.first + d[nod][poz] + v[cop].offsetS << " ( - " << v[nod].offsetS << " ) si lungimea " << i.second + v[cop].offsetL + 1 << " ( - " << v[nod].offsetL << " )\n";
if( v[nod].mp.find(i.first + d[nod][poz] + v[cop].offsetS - v[nod].offsetS) == v[nod].mp.end() ){
v[nod].mp[i.first + d[nod][poz] + v[cop].offsetS - v[nod].offsetS] = i.second + v[cop].offsetL - v[nod].offsetL + 1;
}else{
v[nod].mp[i.first + d[nod][poz] + v[cop].offsetS - v[nod].offsetS] = min(v[nod].mp[i.first + d[nod][poz] + v[cop].offsetS - v[nod].offsetS], i.second + v[cop].offsetL - v[nod].offsetL + 1);
}
}
v[cop].mp.clear();
poz++;
}
v[nod].mp[ 0 - v[nod].offsetS ] = 0 - v[nod].offsetL;
// cout << "Nod = " << nod << " f = " << f << " offsetS = " << v[nod].offsetS << " offsetL = " << v[nod].offsetL << " v[nod].mp =\n";
// for(auto i : v[nod].mp){
// cout << " -- > " << i.first + v[nod].offsetS << " , " << i.second + v[nod].offsetL << '\n';
// }
// cout << " -- > vreau suma " << k - v[nod].offsetS << '\n';
// cout << " -- > mini = " << mini << '\n';
// cout << "am ajung dinou cu nod = " << nod << " f = " << f << '\n';
if(v[nod].mp.find(k - v[nod].offsetS) != v[nod].mp.end()){
// cout << "Sunt la " << nod << " f = " << f << " si am nevoie de suma " << k - v[nod].offsetS << " si are lungimea " << v[nod].mp[ k - v[nod].offsetS ] + v[nod].offsetL << '\n';
if(mini == -1) mini = v[nod].mp[ k - v[nod].offsetS ] + v[nod].offsetL;
else mini = min(mini, v[nod].mp[ k - v[nod].offsetS ] + v[nod].offsetL);
}
// cout << " -- > mini = " << mini << '\n';
}
int best_path(int N, int K, int H[][2], int L[]){
n = N; k = K;
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] );
}
solutie(0, -1);
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];
// out << best_path(n, k, H, L);
// return 0;
// }
