#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2e5;
const int MAXK = 1e6; // learn how to read!!!
const int INF = 1e9;
vector<pair<int, int>> adj[MAXN];
int K, N, ret = -1;
bool vis[MAXN];
int sz[MAXN];
int dist1[MAXK + 1], dist2[MAXK + 1];
vector<int> rev1, rev2;
void calc_sz(int v, int p = -1) {
if (vis[v]) {
sz[v] = 0;
return;
}
sz[v] = 1;
for (auto& [u, w] : adj[v]) {
if (u == p) continue;
calc_sz(u, v);
sz[v] += sz[u];
}
}
int find_cent(int v, int p, int n) {
for (auto& [u, w] : adj[v]) {
if (vis[u] || u == p) continue;
if (sz[u] > n / 2) return find_cent(u, v, n);
}
return v;
}
void dfs(int v, int p, int d = 0, int W = 0) {
if (W > K) return;
dist2[W] = min(dist2[W], d);
rev2.push_back(W);
for (auto& [u, w] : adj[v]) {
if (u == p) continue;
dfs(u, v, d + 1, W + w);
}
}
void work(int v) {
// cerr << "v = " << v << "\n";
calc_sz(v);
int c = find_cent(v, -1, sz[v]);
// cerr << "c = " << c << endl;
vis[c] = 1;
dist1[0] = 0;
rev1.push_back(0);
for (auto& [u, w] : adj[c]) {
if (vis[u]) continue;
dfs(u, c, 1, w);
for (int i : rev2) {
if (dist1[K - i] == INF) continue;
int now = dist1[K - i] + dist2[i];
if (ret == -1 || ret > now) ret = now;
}
// cerr << u << " rev = ";
// for (int i : rev2) cerr << i << " ";
// cerr << endl;
// cerr << u << " vals = ";
// for (int i : rev2) cerr << dist2[i] << " ";
// cerr << endl;
for (int i : rev2) dist1[i] = min(dist1[i], dist2[i]), dist2[i] = INF, rev1.push_back(i);
rev2.clear();
}
for (int i : rev1) dist1[i] = INF;
for (auto& [u, w] : adj[c]) {
if (!vis[u]) {
work(u);
}
}
}
int best_path(int nN, int nK, int H[][2], int L[])
{
K = nK;
N = nN;
for (int i = 0; i <= K; ++i) {
dist1[i] = dist2[i] = INF;
}
for (int i = 0; i + 1 < N; ++i) {
int u = H[i][0];
int v = H[i][1];
adj[u].push_back({v, L[i]});
adj[v].push_back({u, L[i]});
}
work(0);
return ret;
}
//#define MAX_N 500000
//
//static int nN, nK;
//static int H[MAX_N][2];
//static int L[MAX_N];
//static int solution;
//
//inline
//void my_assert(int e) {if (!e) abort();}
//
//void read_input()
//{
// int i;
// my_assert(2==scanf("%d %d",&nN,&nK));
// for(i=0; i<nN-1; i++)
// my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
// my_assert(1==scanf("%d",&solution));
//}
//
//int main()
//{
// int ans;
// read_input();
// ans = best_path(nN,nK,H,L);
// if(ans==solution)
// printf("Correct.\n");
// else
// printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
//
//// return 0;
//}
