#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define tt tuple<int,int,int>
#define NMAX 200005
#define MOD 1000000007
#define INF 1e9
#define matriz vector<vector<int>>
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
vector<pii> g[NMAX];
int sz[NMAX];
map<int,int> best, temp;
bitset<NMAX> exc;
int DFS(int v, int pai) {
sz[v] = 1;
for(auto [it, d] : g[v]) {
if(it == pai || exc[it]) continue;
sz[v] += DFS(it, v);
}
return sz[v];
}
int centroid(int v, int pai, int n) {
for(auto [it, d] : g[v]) {
if(it == pai || exc[it]) continue;
if(sz[it] * 2 > n)
return centroid(it, v, n);
}
return v;
}
void DFS2(int v, int pai, int dist, int nvl, int k) {
if(dist > k) return;
if(!temp.count(dist) || temp[dist] > nvl)
temp[dist] = nvl;
for(auto [it, d] : g[v]) {
if(it == pai || exc[it]) continue;
DFS2(it, v, dist+d, nvl+1, k);
}
}
int solve(int v, int k) {
DFS(v, -1);
int c = centroid(v, -1, sz[v]);
int resp = INF;
best.clear();
for(auto [it, d] : g[c]) {
if(exc[it]) continue;
temp.clear();
DFS2(it, c, d, 1, k);
for(auto [dist, nvl] : temp) {
if(dist == k || best.count(k-dist)) {
resp = min(resp, nvl+best[k-dist]);
}
}
for(auto [dist, nvl] : temp) {
if(!best.count(dist) || nvl < best[dist])
best[dist] = nvl;
}
}
exc.set(c);
for(auto [it, d] : g[c]) {
if(exc[it]) continue;
resp = min(resp, solve(it, k));
}
return resp;
}
int best_path(int n, int k, int h[][2], int l[]) {
for(int i = 0; i < n-1; i++) {
g[h[i][0]].push_back({h[i][1], l[i]});
g[h[i][1]].push_back({h[i][0], l[i]});
}
int resp = solve(0, k);
if(resp == INF) return -1;
return resp;
}
