#include "race.h"
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int M=2e5+10;
vector<pair<long long,int> > adj[M];
int n,rem[M],sz[M],dist[M],lvl[M];
set<pair<long long,int> >::iterator it;
set<pair<long long,int> > s;
queue<pair<long long,int> > q;
int ans=INT_MAX,k;
void findsz(int u,int p){
sz[u]=1;
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i].second;
if(v==p || rem[v]) continue;
findsz(v,u);
sz[u]+=sz[v];
}
}
void findlvl(int u,int p){
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i].second;
if(v==p || rem[v]) continue;
lvl[v]=lvl[u]+1;
findlvl(v,u);
}
}
int getcentroid(int u,int p,int treesz){
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i].second;
if(v==p || rem[v]) continue;
if(sz[v]*2>treesz) return getcentroid(v,u,treesz);
}
return u;
}
void dfs(int u,int p){
if(dist[u]>k) return;
for(int i=0;i<adj[u].size();i++){
if(!lvl[u]) while(!q.empty()) s.insert(mp(k-q.front().first,q.front().second)),q.pop();
int v=adj[u][i].second;
long long w=adj[u][i].first;
if(v==p || rem[v]) continue;
dist[v]=dist[u]+w;
it=s.lower_bound(mp(dist[v],0));
if(it->first==dist[v]) ans=min(ans,it->second+lvl[v]);
q.push(mp(dist[v],lvl[v]));
dfs(v,u);
}
}
void decom(int u){
findsz(u,u);
int cen=getcentroid(u,u,sz[u]);
//cout<<cen <<"\n";
//for(int i=0;i<n;i++) cout<<dist[i] <<" ";
s.insert(mp(k,0));
lvl[cen]=0;
dist[cen]=0;
findlvl(cen,cen);
dfs(cen,cen);
s.clear();
while(!q.empty()) q.pop();
rem[cen]=true;
for(int i=0;i<adj[cen].size();i++){
int v=adj[cen][i].second;
if(rem[v]) continue;
decom(v);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n=N,k=K;
for(int i=0;i<n-1;i++){
adj[H[i][0]].push_back(mp(L[i],H[i][1]));
adj[H[i][1]].push_back(mp(L[i],H[i][0]));
}
decom(0);
if(ans==INT_MAX) return -1;
return ans;
}
