#include <bits/stdc++.h>
using namespace std;
bool remov[200005];
int sz[200005];
int Z;
int res = 1000000000;
vector<pair<int, int>> g[200005];
stack<pair<int, int>> s1;
stack<int> s2;
int su[1000005];
int centroid(int x, int tam, int p=-1) {
for(pair<int, int> y : g[x]) {
if(y.first == p || remov[y.first]) continue;
if(sz[y.first]*2 > tam) return centroid(y.first, tam, x);
}
return x;
}
int subtree(int x, int p=-1) {
for(pair<int, int> y : g[x]) {
if(y.first == p || remov[y.first]) continue;
sz[x] += subtree(y.first, x);
}
return sz[x];
}
void dfs(int x, int p, int dist, int cont) {
if(dist > Z) return;
if(dist == Z) {
res = min(res, cont);
return;
}
if(su[Z-dist] > 0) {
res = min(res, su[Z-dist]+cont);
}
//su[dist] = min(cont, su[dist]);
s1.push({dist, cont});
s2.push(dist);
for(pair<int, int> y : g[x]) {
if(y.first == p || remov[y.first]) continue;
dfs(y.first, x, dist+y.second, cont+1);
}
}
int xd;
pair<int, int> lol;
void centdecomp(int x) {
int cent = centroid(x, subtree(x));
for(pair<int, int> y : g[cent]) {
if(remov[y.first]) continue;
while(!s1.empty()) {
lol = s1.top();
s1.pop();
su[lol.first] = min(su[lol.first], lol.second);
}
dfs(y.first, x, y.second, 1);
}
while(!s2.empty()) {
xd = s2.top();
s2.pop();
su[xd] = 0;
}
remov[cent] = true;
for(pair<int, int> y : g[x]) {
if(remov[y.first]) continue;
centdecomp(y.first);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for(int i=0; i<N; i++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
Z = K;
centdecomp(0);
if(res == 1000000000) return -1;
return res;
}
