#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
const int MAXK = 1e6+5;
// OVERALL
int K;
int mn = INT_MAX;
// GRAPH
vector<pair<int,int>> adj[MAXN];
// CENTROID
vector<int> child_centroid[MAXN];
int sz[MAXN];
int vis[MAXN];
// CAL DIST
int dist[MAXK];
pair<int,int> rollback_list[MAXN];
int rollback_ptr = 0;
int rolldist[MAXN];
int rolldist_ptr = 0;
void init(){
fill(adj,adj+MAXN,vector<pair<int,int>>());
fill(child_centroid,child_centroid+MAXN,vector<int>());
memset(sz,0,sizeof(sz));
memset(vis,0,sizeof(vis));
fill(dist,dist+MAXN,INT_MAX/3);
memset(rollback_list,0,sizeof(rollback_list));
rollback_ptr = 0;
memset(rolldist,0,sizeof(rolldist));
rolldist_ptr = 0;
}
// CENTROID
int get_centriod(int u,int p,int n){
for(auto x : adj[u]){
int v = x.first;
if(v == p || vis[v]) continue;
if(sz[v] > n/2){
return get_centriod(v,u,n);
}
}
return u;
}
void get_size(int u,int p){
sz[u] = 1;
for(auto x : adj[u]){
int v = x.first;
if(v == p || vis[v]) continue;
get_size(v,u);
sz[u] += sz[v];
}
}
int construct_centroid(int u,int p,int l){
get_size(u,p);
int n = sz[u];
int cen = get_centriod(u,p,n);
vis[cen] = 1;
for(auto x : adj[cen]){
int v = x.first;
if(vis[v]) {
continue;
}
child_centroid[cen].push_back(construct_centroid(v,cen,l+1));
}
return cen;
}
void dfs(int u,int p,int cnt,int cost){
if(cost > K) return;
if(cost == K) mn = min(mn,cnt);
else if(dist[K-cost] != INT_MAX) mn = min(mn,dist[K-cost] + cnt);
rollback_list[rollback_ptr++] = {cnt,cost};
rolldist[rolldist_ptr++] = cost;
for(auto x : adj[u]){
if(x.first == p || vis[x.first]) continue;
dfs(x.first,u,cnt+1,cost+x.second);
}
}
void cal_centroid(int u){
if(child_centroid[u].empty()) return;
vis[u] = 1;
for(int v : child_centroid[u]){
cal_centroid(v);
}
for(auto x : adj[u]){
dfs(x.first,u,1,x.second);
while(rollback_ptr > 0){
rollback_ptr--;
dist[rollback_list[rollback_ptr].second] = rollback_list[rollback_ptr].first;
}
}
while(rolldist_ptr > 0){
rolldist_ptr--;
rolldist[rolldist_ptr] = INT_MAX;
}
vis[u] = 0;
}
int best_path(int N, int _K, int H[][2], int L[])
{
init();
K = _K;
for(int i = 0;i < N-1;i++){
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
int cen = construct_centroid(0,-1,1);
memset(vis,0,sizeof(vis));
cal_centroid(cen);
if(mn == INT_MAX) return -1;
return mn;
}
// #define MAX_N 500000
// static int N, P;
// 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",&N,&P));
// for(i=0; i<N-1; i++)
// my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
// }
// int main()
// {
// int ans;
// read_input();
// ans = best_path(N,P,H,L);
// cout << ans << '\n';
// return 0;
// }
// /*
// 11 12
// 0 1 3
// 0 2 4
// 2 3 5
// 3 4 4
// 4 5 6
// 0 6 3
// 6 7 2
// 6 8 5
// 8 9 6
// 8 10 7
// */
