//#include "race.h"
#include <bits/stdc++.h>
using namespace std;
static const int MAXN=200002;
vector<pair<int,int>> adj[MAXN];
bool rnd[MAXN];
int subsz[MAXN];
int prtnd[MAXN];
long long answer;
long long targetK;
void bldcp(int start,vector<int>& nodes) {
nodes.clear();
stack<int> st;
st.push(start);
prtnd[start]=-1;
while (!st.empty()) {
int u=st.top();
st.pop();
nodes.push_back(u);
for (auto [v,w]:adj[u]) {
if (rnd[v] || v==prtnd[u]) continue;
prtnd[v]=u;
st.push(v);
}
}
}
void cmpsz(const vector<int>& nodes) {
for (int i=(int)nodes.size()-1;i>=0;i--) {
int u=nodes[i];
subsz[u]=1;
for (auto [v,w]:adj[u]) {
if (rnd[v]) continue;
if (prtnd[v]==u) subsz[u]+=subsz[v];
}
}
}
int fndcrt(const vector<int>& nodes) {
int total=(int)nodes.size();
int centroid=-1;
int bstbal=total+1;
for (int u:nodes) {
int mx=total-subsz[u];
for (auto [v,w]:adj[u]) {
if (rnd[v]) continue;
if (prtnd[v]==u) mx=max(mx,subsz[v]);
}
if (mx<bstbal) {
bstbal=mx;
centroid=u;
}
}
return centroid;
}
void clctpth(int start,int blocked,long long dist0,int edges0,vector<pair<long long,int>>& paths) {
stack<tuple<int,int,long long,int>> st;
st.push({start,blocked,dist0,edges0});
while (!st.empty()) {
auto [u,p,dist,edges]=st.top();
st.pop();
if (dist>targetK) continue;
paths.push_back({dist,edges});
for (auto [v,w]:adj[u]) {
if (v==p || rnd[v]) continue;
st.push({v,u,dist+w,edges+1});
}
}
}
void decomp(int entry) {
vector<int> nodes;
bldcp(entry,nodes);
cmpsz(nodes);
int c=fndcrt(nodes);
rnd[c]=true;
unordered_map<long long,int> best;
best.reserve(nodes.size()*2+10);
best[0]=0;
for (auto [v,w]:adj[c]) {
if (rnd[v]) continue;
vector<pair<long long,int>> paths;
clctpth(v,c,w,1,paths);
for (auto [dist,edges]:paths) {
auto it=best.find(targetK-dist);
if (it!=best.end()) answer=min(answer,(long long)edges+it->second);
}
for (auto [dist,edges] : paths) {
auto it=best.find(dist);
if (it==best.end() || edges<it->second) best[dist]=edges;
}
}
for (auto [v,w]:adj[c]) if (!rnd[v]) decomp(v);
}
int best_path(int n,int k,int h[][2],int l[]) {
targetK=k;
answer=(long long)4e18;
for (int i=0;i<n;i++) {
adj[i].clear();
rnd[i]=false;
}
for (int i=0;i<n-1;i++) {
int u=h[i][0];
int v=h[i][1];
int w=l[i];
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
decomp(0);
if (answer==(long long)4e18) return -1;
return (int)answer;
}
