#include "race.h"
#include <bits/stdc++.h>
constexpr int N = 2e5;
int n, k, ans = 1e9;
int siz[N], del[N];
std::vector<std::pair<int, int>> path;
std::vector<std::vector<std::pair<int, int>>> e(N);
int dfs(int u, int p = -1) {
siz[u] = 1;
for (auto [v, w] : e[u]) {
if (del[v] || v == p)
continue;
siz[u] += dfs(v, u);
}
return siz[u];
}
void dfs2(int u, int dep, int len, int p) {
path.emplace_back(len, dep);
for (auto [v, w] : e[u]) {
if (del[v] || v == p)
continue;
dfs2(v, dep + 1, len + w, u);
}
}
int Cen(int u, int S, int p = -1) {
for (auto [v, w] : e[u]) {
if (del[v] || v == p)
continue;
if (2 * siz[v] > S)
return Cen(v, S, u);
}
return u;
}
void Decompose(int u) {
int c = Cen(u, dfs(u));
std::map<int, int> dp, vis;
vis[0] = 1;
for (auto [v, w] : e[c]) {
if (del[v])
continue;
path.clear();
dfs2(v, 1, w, c);
for (auto [len, dep] : path) {
if (len > k)
continue;
if (vis[k - len])
ans = std::min(ans, dep + dp[k - len]);
}
for (auto [len, dep] : path) {
if (len > k)
continue;
if (vis[len] == 0 || dep < dp[len])
dp[len] = dep;
vis[len] = 1;
}
}
del[c] = 1;
for (auto [v, w] : e[c]) {
if (!del[v])
Decompose(v);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for (int i = 0; i < n - 1; i++) {
int u = H[i][0], v = H[i][1], w = L[i];
std::cout << u << ' ' << v << ' ' << w << '\n';
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
Decompose(0);
return ans == 1e9 ? -1 : ans;
}
// int main() {
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
// std::cin >> n >> k;
// for (int i = 0; i < n - 1; i++) {
// int u, v, w;
// std::cin >> u >> v >> w;
// e[u].emplace_back(v, w);
// e[v].emplace_back(u, w);
// }
// Decompose(0);
// std::cout << (ans == 1e9 ? -1 : ans) << '\n';
// }
