#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pii pair<ll, ll>
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
ll N, K;
vector<vector<pii>> graph;
vector<ll> sz;
vector<bool> vis;
gp_hash_table<ll, ll> short_pth;
const ll INF = 1e14;
ll find_size(ll v, ll p = -1) {
sz[v] = 1;
for(pii e : graph[v]) {
ll u = e.first;
if(vis[u] || u == p) continue;
sz[v] += find_size(u, v);
}
return sz[v];
}
ll find_centroid(ll v, ll p, ll n) {
for(pii e : graph[v]) {
ll u = e.first;
if(u == p || vis[u]) continue;
if(sz[u] > n / 2) return find_centroid(u, v, n);
}
return v;
}
void find_bst_path(ll v, ll p, ll w, ll d, ll &bst_path, bool upd) {
if(w > K) return;
if(upd)
short_pth[w] = min(short_pth.find(w) != short_pth.end() ? short_pth[w] : INF, d);
else if(short_pth.find(K - w) != short_pth.end())
bst_path = min(bst_path, d + short_pth[K - w]);
for(pii u : graph[v]) {
if(vis[u.first] || u.first == p) continue;
find_bst_path(u.first, v, w + u.second, d + 1, bst_path, upd);
}
}
void centroid(ll v, ll &bst_path) {
find_size(v);
ll c = find_centroid(v, -1, sz[v]);
vis[c] = true;
short_pth[0] = 0;
for(pii e : graph[c]) {
ll u = e.first;
if(vis[u]) continue;
find_bst_path(u, c, e.second, 1, bst_path, false);
find_bst_path(u, c, e.second, 1, bst_path, true);
}
short_pth.clear();
for(pii e : graph[c]) {
ll u = e.first;
if(!vis[u]) centroid(u, bst_path);
}
}
int best_path(int n, int k, int H[][2], int L[])
{
N = n; K = k;
graph.resize(N);
sz.resize(N);
vis.resize(N, false);
for(ll i = 0; i < N - 1; i++) {
graph[H[i][0]].push_back({H[i][1], L[i]});
graph[H[i][1]].push_back({H[i][0], L[i]});
}
ll bst_path = INF;
centroid(0, bst_path);
return bst_path == INF ? -1 : bst_path;
}
// signed main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// ll n, k;
// cin >> n >> k;
// ll H[n - 1][2], L[n - 1];
// for(ll i = 0; i < n - 1; i++) {
// cin >> H[i][0] >> H[i][1] >> L[i];
// }
// ll sol; cin >> sol;
// ll bst = best_path(n, k, H, L);
// cout << "AC Solution : " << sol << endl;
// cout << "User Solution : " << bst << endl;
// }
