#pragma GCC optimize ("Ofast", "unroll-loops")
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
using namespace std;
const int NMAX = 200002;
using ll = long long;
const int INF = 1e9;
struct muchii {
int nod, dist;
};
vector <vector <muchii>> v;
int n, k;
bool f[NMAX]; ///dc deja am procesat ca centroid respectivul sau nu
int parent[NMAX];
int weight[NMAX]; ///ce weight are subarb resp
void dfssize(int start) {
weight[start] = 1;
for(const auto& x : v[start]) {
if(x.nod == parent[start] || f[x.nod])
continue;
parent[x.nod] = start;
dfssize(x.nod);
weight[start] += weight[x.nod];
}
}
int centroid = -1;
bool dfscentroid(int start, int tot) { ///sizeul e de sus
bool ok = false;
if(tot - weight[start] > tot / 2)
ok = 1;
for(const auto& x : v[start]) {
if(x.nod == parent[start] || f[x.nod])
continue;
if(weight[x.nod] > tot / 2)
ok = true;
}
if(!ok) { ///am gasit centroidul
centroid = start;
return true;
}
for(const auto& x : v[start]) {
if(x.nod == parent[start] || f[x.nod])
continue;
if (dfscentroid(x.nod, tot)) {
return true;
}
}
return false;
}
map <int, int> umap, full; ///full pt centroid, umap pt fiul curent
int ans = INF; ///dist minima pt suma k
void updateans(int copil) { ///start e copilul, actually
/* for (const auto& var : umap) {
cout << var.first << " " << var.second << "\n";
}*/
if(umap.find(k) != umap.end()) ///dc deja e lant pana in el
ans = min(ans, umap[k]);
for(const auto& var : umap) { ///ce val am pastrat in copil
if(var.second > ans)
continue;
///COMPARAM cu ce avem de la vechii fii
if(full.find(k - var.first) != full.end())
ans = min(ans, full[k - var.first] + var.second);
}
for(const auto& var : umap) { ///UPDATAM
if(var.first > k || var.second > ans)
continue;
if(full.find(var.first) != full.end())
full[var.first] = min(full[var.first], var.second);
else
full[var.first] = var.second;
}
}
void dfsans(int start, int add, int muchii) { ///formam dist de la noduri la centroid
if(muchii >= ans || add > k) ///deja e drum prea lung
return;
if(umap.find(add) != umap.end())
umap[add] = min(umap[add], muchii);
else
umap[add] = muchii;
for(const auto& x : v[start]) {
if(x.nod == parent[start] || f[x.nod])
continue;
dfsans(x.nod, add + x.dist, muchii + 1);
}
}
void build(int start) { ///de la subarborele lui start INCEPEM
parent[start] = -1;
dfssize(start);
centroid = -1;
dfscentroid(start, weight[start]);
//cout << centroid << " " << weight[start] << "\n";
parent[centroid] = -1; ///rebuild in subarborele nostru sizeurile de parinti etc
dfssize(centroid); ///reindexam parintii basically
full.clear();
for(const auto& x : v[centroid]) {
if(f[x.nod])
continue;
umap.clear();
dfsans(x.nod, x.dist, 1); ///formezi drumurile
updateans(x.nod); ///unim fiul si si comparam
}
//cout << start << " " << centroid << " " << ans << '\n';
f[centroid] = 1;
//cout << "\n";
for(const auto& x : v[centroid]) { ///facem si in subarbori
if(!f[x.nod])
build(x.nod);
}
}
int best_path(int N, int K, int h[NMAX][2], int l[NMAX]) {
n = N, k = K;
v.resize(n + 1);
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++) {
cout << "nodul " << i << '\n';
for(auto x : v[i])
cout << x.nod << " ";
cout << '\n';
}*/
build(0);
if(ans == INF)
ans = -1;
return ans;
}
/*
int h[NMAX][2];
int l[NMAX];
int main()
{
freopen("race.in", "r", stdin);
freopen("race.out", "w", stdout);
int N, K;
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);
return 0;
}*/
