#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5+10;
const int K = 1e6+100;
const int INF = 1e9+10;
int n, k, sub[N], mn[K+10];
vector<pii> G[N];
bool rm[N];
void pre(int v, int p) {
sub[v]=1;
for (auto u : G[v]) {
if (u.first == p || rm[u.first]) continue;
pre(u.first, v);
sub[v]+=sub[u.first];
}
}
int cent(int v, int p, int sz) {
int x=-1; bool ok=2*(sz-sub[v]) <= sz;
for (auto u : G[v]) {
if (u.first == p || rm[u.first]) continue;
if (sub[u.first]*2 > sz) ok=false;
int r=cent(u.first, v, sz);
if (r > -1) x=r;
}
if (ok) x=v;
return x;
}
int add(int v, int p, int dt, ll s) {
int res=INF;
if (s <= k) res=min(res, dt+mn[k-s]);
for (auto u : G[v]) {
if (u.first == p || rm[u.first]) continue;
res=min(res, add(u.first, v, dt+1, s+u.second));
}
if (s <= k) mn[s]=min(mn[s], dt);
return res;
}
void rem(int v, int p, ll s) {
if (s <= k) mn[s]=INF;
for (auto u : G[v]) {
if (u.first == p || rm[u.first]) continue;
rem(u.first, v, s+u.second);
}
}
int solve(int v) {
pre(v, v); int sz=sub[v];
int r=cent(v, v, sz);
int ans=INF; rm[r]=true;
for (auto u : G[r]) {
if (rm[u.first]) continue;
ans=min(ans, add(u.first, r, 1, u.second));
}
for (auto u : G[r]) {
if (rm[u.first]) continue;
rem(u.first, r, u.second);
}
for (auto u : G[r]) {
if (rm[u.first]) continue;
ans=min(ans, solve(u.first));
} return ans;
}
int best_path(int sz, int l, int h[][2], int w[]) {
n=sz, k=l;
for (int i=0; i<=K; ++i) mn[i]=INF;
for (int i=0; i<n-1; ++i) {
int a=h[i][0]+1, b=h[i][1]+1;
G[a].push_back({b, w[i]});
G[b].push_back({a, w[i]});
}
int x=solve(1);
if (x < INF) return x;
return -1;
}
/*
#define MAX_N 500000
static int nv, kv;
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",&nv,&kv));
for(i=0; i<nv-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(nv,kv,H,L);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}*/
