#include <bits/stdc++.h>
#include <race.h>
using i64 = long long;
constexpr int maxN = 2E5 + 5;
int N, K;
std::vector<std::pair<int, int>> adj[maxN];
std::vector<bool> active;
std::vector<int> sz;
int ans = maxN;
int csizes(int v, int p) {
sz[v] = 1;
for(auto [u, w] : adj[v]) {
if(u == p || !active[u]) {
continue;
}
sz[v] += csizes(u, v);
}
return sz[v];
}
int gcent(int v, int p, int S) {
for(auto [u, w] : adj[v]) {
if(p == u || !active[u]) {
continue;
}
if(sz[u] * 2 > S) {
return gcent(u, v, S);
}
}
return v;
}
std::map<int, int> mp;
void paint(int v, int p, int d, int h, bool fill) {
if(h > K) {
return;
}
if(fill) {
if(!mp.count(h)) {
mp[h] = d;
} else {
mp[h] = std::min(mp[h], d);
}
} else {
int t = K - h;
if(mp.count(t)) {
ans = std::min(ans, d + mp[t]);
}
}
for(auto [u, w] : adj[v]) {
if(u == p || !active[u]) {
continue;
}
paint(u, v, d + 1, h + w, fill);
}
}
void decomp(int v) {
v = gcent(v, v, csizes(v, v));
active[v] = false;
mp.clear();
mp[0] = 0;
for(auto [u, w] : adj[v]) {
if(!active[u]) {
continue;
}
paint(u, v, 1, w, 0);
paint(u, v, 1, w, 1);
}
for(auto [u, w] : adj[v]) {
if(!active[u]) {
continue;
}
decomp(u);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
::N = N;
::K = K;
active.resize(N, true);
sz.resize(N);
for(int i = 0; i < N - 1; i++) {
// std::cerr << H[i][0] << " " << H[i][1] << " :: " << L[i] << "\n";
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
decomp(0);
if(ans == maxN) {
ans = -1;
}
return ans;
}
