#include <bits/stdc++.h>
using namespace std;
const int MAXN=200002;
const long long INF=1e18;
int n;
long long k;
vector<pair<int,int>> adj[MAXN];
bool removed[MAXN];
int sbtrsz[MAXN];
long long answer=INF;
void dfs_size(int u,int p) {
sbtrsz[u]=1;
for (auto [v,w]:adj[u]) {
if (v==p || removed[v]) continue;
dfs_size(v,u);
sbtrsz[u]+=sbtrsz[v];
}
}
int dfscent(int u,int p,int total) {
for (auto [v,w]:adj[u]) {
if (v==p || removed[v]) continue;
if (sbtrsz[v]>total/2) return dfscent(v,u,total);
}
return u;
}
void dfs_collect(int u,int p,long long dist,int edges,vector<pair<long long,int>> &vec) {
if (dist>k) return;
vec.push_back({dist,edges});
for (auto [v,w]:adj[u]) {
if (v==p || removed[v]) continue;
dfs_collect(v,u,dist+w,edges+1,vec);
}
}
void decomp(int entry) {
dfs_size(entry,-1);
int c=dfscent(entry,-1,sbtrsz[entry]);
removed[c]=true;
map<long long,int> bsted;
bsted[0]=0;
for (auto [v,w]:adj[c]) {
if (removed[v]) continue;
vector<pair<long long,int>> paths;
dfs_collect(v,c,w,1,paths);
for (auto [d,e]:paths) if (bsted.count(k-d)) answer=min(answer,(long long)e+bsted[k-d]);
for (auto [d,e]:paths) {
if (!bsted.count(d)) bsted[d]=e;
else bsted[d]=min(bsted[d],e);
}
}
for (auto [v,w]:adj[c]) if (!removed[v]) decomp(v);
}
int best_path(int n,int k,int h[][2],int l[]) {
n=n;
k=k;
for (int i=0;i<n;i++) adj[i].clear();
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});
}
memset(removed,false,sizeof(removed));
answer=INF;
decomp(0);
if (answer==INF) return -1;
return (int)answer;
}
