#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
vector <pair <int, int> > v[maxn];
set <pair <int, int> > s[maxn];
set <pair <int, int> > :: iterator it, it2;
map <int, int> m[maxn];
int ans = 1e9, parent[maxn];
int find (int x){
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void unite (int x, int y, int d, int k){
//cout << "unite " << x << " " << y << " " << d << " " << k << endl;
if (s[x].size() < s[y].size()) swap(x, y);
parent[y] = x;
for (it = s[y].begin(); it != s[y].end(); it++){
int duzina = it -> first;
duzina += d;
int vrhovi = it -> second;
if (m[x][k - duzina] != 0) ans = min(ans, m[x][k - duzina] + vrhovi);
}
for (it = s[y].begin(); it != s[y].end(); it++){
int duzina = it -> first;
duzina += d;
int vrhovi = it -> second;
vrhovi++;
if (duzina <= k){
//cout << duzina << " " << vrhovi << endl;
it2 = s[x].lower_bound({duzina, 0});
if (it2 != s[x].end() and it2 -> first == duzina and (it2 -> second) > vrhovi){
s[x].erase(it2);
s[x].insert({duzina, vrhovi});
m[x][duzina] = vrhovi;
}
else if ((it2 == s[x].end()) or ((it2 -> first) != duzina)){
s[x].insert({duzina, vrhovi});
m[x][duzina] = vrhovi;
}
}
}
if (m[x][k] != 0) ans = min(ans, m[x][k]);
s[y].clear();
m[y].clear();
}
void dfs (int x, int p, int k){
for (int i = 0; i < v[x].size(); i++){
int y = v[x][i].first;
int d = v[x][i].second;
if (y != p){
dfs(y, x, k);
//cout << "spajam " << x << " " << y << endl;
int px = find(x);
int py = find(y);
unite(px, py, d, k);
}
}
}
int best_path (int n, int k, int h[maxn][2], int l[maxn]){
for (int i = 0; i < n - 1; i++){
v[h[i][0]].push_back({h[i][1], l[i]});
v[h[i][1]].push_back({h[i][0], l[i]});
}
for (int i = 0; i < n; i++) s[i].insert({0, 1}), m[i][0] = 1, parent[i] = i;
dfs(0, 0, k);
if (ans == 1e9) return -1;
else return ans - 1;
}
/*
int main (void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, k, h[maxn][2], l[maxn];
cin >> n >> k;
for (int i = 0; i < n - 1; i++) cin >> h[i][0] >> h[i][1] >> l[i];
cout << best_path(n, k, h, l) << endl;
return 0;
}*/
