#include "race.h"
#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
vector<pair<int,int>> adj[200000];
int M, D[1000001], P[1000001], W[200000], dist[200000];
void reset(int c)
{
W[c]=0;
for(auto[n,w]: adj[c]) if(W[n]>0) reset(n);
}
int dfs(int c)
{
W[c]=1; dist[c]=0x7fffffff;
for(auto[n,w]: adj[c]) if(W[n]==0) W[c]+=dfs(n);
return W[c];
}
int centroid(int c, int v)
{
for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]>v) return centroid(n,v);
return c;
}
int solve(int C)
{
int ret=0x7fffffff;
queue<pair<int,int>> Q;
reset(C);
dist[C=centroid(C,dfs(C))]=0;
D[0]=0;
P[0]=C;
for(auto[n,w]: adj[C]) {
dist[n]=w;
if(dist[n]>M) continue;
if(P[M-dist[n]]==C) ret=min(ret,1+D[M-dist[n]]);
Q.emplace(1,n);
while(!Q.empty()) {
auto[v,c]=Q.front();
Q.pop();
for(auto[n,w]: adj[c]) if(dist[n]>dist[c]+w && dist[c]+w<=M) {
dist[n]=dist[c]+w;
if(P[M-dist[n]]==C) ret=min(ret,v+1+D[M-dist[n]]);
Q.emplace(v+1,n);
}
}
Q.emplace(1,n);
while(!Q.empty()) {
auto[v,c]=Q.front();
Q.pop();
if(P[dist[c]]!=C) {
P[dist[c]]=C;
D[dist[c]]=v;
}
else D[dist[c]]=min(D[dist[c]],v);
for(auto[n,w]: adj[c]) if(dist[n]==dist[c]+w) Q.emplace(v+1,n);
}
}
W[C]=-1;
for(auto[n,w]: adj[C]) if(W[n]>0) ret=min(ret,solve(n));
return ret;
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i=0;i<N-1;i++) {
adj[H[i][0]].emplace_back(H[i][1],L[i]);
adj[H[i][1]].emplace_back(H[i][0],L[i]);
}
memset(P,-1,sizeof(P));
M=K;
N=solve(0);
return N==0x7fffffff ? -1:N;
}
