#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int MAXN=200009,INF=1000000009;
int dist[1000009];
int siz[MAXN];
bool was[MAXN];
int X;
vector<int> za_brisati;
vector<pair<int,int>> graf[MAXN];
int init_siz(int node,int pret){
siz[node]=1;
for(auto x:graf[node]){
if(x.first==pret||was[x.first]) continue;
siz[node]+=init_siz(x.first,node);
}
return siz[node];
}
int Centroid(int node,int pret,int n){
for(auto x:graf[node]){
if(x.first==pret||was[x.first]) continue;
if(siz[x.first]*2>n) return Centroid(x.first,node,n);
}
return node;
}
int rez=INF;
void C_query(int node,int pret,int tr_dist,int brojac){
if(tr_dist>X) return;
za_brisati.push_back(tr_dist);
rez=min(rez,brojac+dist[X-tr_dist]);
for(auto x:graf[node]){
if(x.first==pret||was[x.first]) continue;
C_query(x.first,node,tr_dist+x.second,brojac+1);
}
}
void C_upd(int node,int pret,int tr_dist,int brojac){
if(tr_dist>X) return;
dist[tr_dist]=min(dist[tr_dist],brojac);
for(auto x:graf[node]){
if(x.first==pret||was[x.first]) continue;
C_upd(x.first,node,tr_dist+x.second,brojac+1);
}
}
void CD(int poc){
int n=init_siz(poc,-1);
int C=Centroid(poc,-1,n);
dist[0]=0;
for(auto x:graf[C]){
if(was[x.first]) continue;
C_query(x.first,C,x.second,1);
C_upd(x.first,C,x.second,1);
}
for(auto x:za_brisati) dist[x]=INF;
za_brisati.clear();
was[C]=1;
for(auto x:graf[C]){
if(was[x.first]) continue;
CD(x.first);
}
}
int best_path(int N, int K, int H[][2], int L[]){
X=K;
for(int i=0; i<1000009; i++) dist[i]=INF;
for(int i=0; i<N-1; i++){
int a=H[i][0],b=H[i][1],w=L[i];
graf[a].push_back({b,w});
graf[b].push_back({a,w});
}
CD(0);
if(K==0) return 0;
return (rez<MAXN?rez:-1);
}
