// #pragma GCC optimize("O3","unrolled-loop")
#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+MAXK,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];
}
}
void dfs(int u,int p,int cnt,int cost){
if(cost > K) return;
if(dist[K-cost] != INT_MAX/3) 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){
get_size(u,-1);
u = get_centriod(u,-1,sz[u]);
vis[u] = 1;
dist[0] = 0;
for(auto x : adj[u]){
dfs(x.first,u,1,x.second);
while(rollback_ptr > 0){
rollback_ptr--;
dist[rollback_list[rollback_ptr].second] = min(dist[rollback_list[rollback_ptr].second],rollback_list[rollback_ptr].first);
}
}
dist[0] = INT_MAX/3;
// while(rolldist_ptr > 0){
// rolldist_ptr--;
// dist[rolldist[rolldist_ptr]] = INT_MAX/3;
// }
while(rolldist_ptr > 0) dist[rolldist[--rolldist_ptr]] = INT_MAX/3;
for(auto x : adj[u]) if(!vis[x.first]) cal_centroid(x.first);
// for(auto x : adj[u]){
// if(vis[x.first]) continue;
// cal_centroid(x.first);
// }
}
/*
void cal_centroid(int u){
get_size(u,-1);
u = get_centriod(u,-1,sz[u]);
vis[u] = 1;
dist[0] = 0;
rolldist[rolldist_ptr++] = 0; // Push 0 here so the while loop cleans it
for(auto x : adj[u]){
if(vis[x.first]) continue;
dfs(x.first,u,1,x.second);
while(rollback_ptr > 0){
rollback_ptr--;
int d = rollback_list[rollback_ptr].second;
int c = rollback_list[rollback_ptr].first;
dist[d] = min(dist[d], c);
}
}
while(rolldist_ptr > 0) dist[rolldist[--rolldist_ptr]] = INT_MAX/3;
for(auto x : adj[u]) if(!vis[x.first]) cal_centroid(x.first);
}
*/
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]});
}
cal_centroid(0);
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
// */
