#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define push_back emplace_back
typedef long long Int;
typedef long double Real;
const int MOD = 2004010501;//>2e9
const int INF = 1e9;
const int MAXN = 2e5 + 500;
int num_nodes, capa;
typedef pair<int,int> Edge;
vector<Edge> graph[MAXN];
vector<int> adj[MAXN];
bool cut[MAXN];
int cnt[MAXN], par[MAXN];
void get_force(int u) {
cnt[u] = 1;
for (int v : adj[u])
if (v != par[u] and !cut[v])
par[v] = u,
get_force(v), cnt[u] += cnt[v];
}
int answer = INF;
const int MAXV = 1e6 + 500;
int best[MAXV], weight[MAXN], depth[MAXN];
int upd_list[MAXN], ptL, ptR;
void find_path(int u, int pa) {
if (weight[u] > capa) return ;
for (auto e : graph[u]) {
const int& v = e.first;
if (v == pa or cut[v]) continue;
weight[v] = weight[u] + e.second;
depth[v] = depth[u] + 1;
find_path(v, u);
}
// if (best[capa - weight[u]] + depth[u] < answer) {
// cerr << "(" << u << ',' << depth[u] << ") with " << best[capa - weight[u]] << '\n';
// }
answer = min(answer, best[capa - weight[u]] + depth[u]);
upd_list[++ptR] = u;
}
void centroid_decomp(int u) {
// cerr << "In subtree ROOT " << u << '\n';
// fill(cnt, cnt + 1 + MAXN, 0);
const int root = u;
get_force(root);
// cerr << "Force = " << cnt[u] << '\n';
int cand; do {
cand = -1;
for (int v : adj[u])
if (!cut[v]) {
int count_sub = (v == par[u]) ? (cnt[root] - cnt[u]) : cnt[v];
if (count_sub > cnt[root] / 2)
{ cand = v; break; }
}
if (cand != -1) u = cand; else break;
} while (true);
// cerr << "CENTROID = " << u << '\n';
cut[u] = true;
ptL = 1; ptR = 0;
for (auto e : graph[u]) {
const int& v = e.first;
// cerr << "BRANCH " << v << '\n';
weight[v] = e.second, depth[v] = 1,
find_path(v, u);
for (; ptL <= ptR; ) {
int x = upd_list[ptL++];
best[weight[x]] = min(best[weight[x]], depth[x]);
}
}
//reset
for (int x,i = 1; i <= ptR; i++)
x = upd_list[i], best[weight[x]] = INF;
// cerr << " -> " << answer << '\n';
//recursion
for (int v : adj[u])
if (!cut[v]) centroid_decomp(v);
}
int best_path(int N, int K, int H[][2], int L[])
{
num_nodes = N;
capa = K;
for (int u, v, w, i = 0; i < num_nodes - 1; i++) {
cin >> u >> v >> w;
u = H[i][0], v = H[i][1], w = L[i];
adj[u].push_back(v),
adj[v].push_back(u);
graph[u].push_back(Edge(v, w)),
graph[v].push_back(Edge(u, w));
}
fill(best + 1, best + MAXV, INF);
centroid_decomp(0);
if (answer == INF) answer = -1;
return answer;
}
