#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const int MAXK = 1e6;
int N, K;
vector<pii> adj[MAXN+10];
bool del[MAXN+10];
int sz[MAXN+10], ans=987654321;
void getsz(int now, int bef)
{
sz[now]=1;
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
getsz(nxt.first, now);
sz[now]+=sz[nxt.first];
}
}
int getcen(int now, int bef, int tot)
{
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
if(sz[nxt.first]>tot/2) return getcen(nxt.first, now, tot);
}
return now;
}
int M[MAXK+10];
vector<int> V;
void dfs1(int now, int bef, ll dist, int road)
{
if(K-dist>=0) ans=min(ans, M[K-dist]+road);
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
dfs1(nxt.first, now, dist+nxt.second, road+1);
}
}
void dfs2(int now, int bef, ll dist, int road)
{
if(dist<=K) M[dist]=min(M[dist], road), V.push_back(dist);
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
dfs2(nxt.first, now, dist+nxt.second, road+1);
}
}
void decomp(int now)
{
getsz(now, now);
now=getcen(now, now, sz[now]);
del[now]=true;
M[0]=0; V.clear();
for(auto nxt : adj[now])
{
if(del[nxt.first]) continue;
dfs1(nxt.first, nxt.first, nxt.second, 1);
dfs2(nxt.first, nxt.first, nxt.second, 1);
}
for(auto it : V) M[it]=987654321;
for(auto nxt : adj[now])
{
if(del[nxt.first]) continue;
decomp(nxt.first);
}
}
int best_path(int _N, int _K, int H[][2], int L[])
{
int i, j;
N=_N; K=_K;
for(i=0; i<N-1; i++)
{
int u, v, w;
u=H[i][0]+1; v=H[i][1]+1; w=L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for(i=0; i<=K; i++) M[i]=987654321;
decomp(1);
if(ans==987654321) ans=-1;
return ans;
}
