#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int MAX_N = 2e5 + 5;
const int MAX_K = 1e6 + 5;
vector<vector<pair<int,int>>> g (MAX_N);
vector<int> sub(MAX_N), dist(MAX_K, 1e9), del(MAX_N);
int ans = 1e9;
int calc_sub(int node, int p) {
sub[node] = 1;
for (auto to : g[node]) {
if (!del[to.first] && to.first != p) {
sub[node] += calc_sub(to.first, node);
}
}
return sub[node];
}
int calc_centroid(int node, int p, int tam) {
for (auto to : g[node]) {
if (!del[to.first] && to.first != p && sub[to.first] > tam / 2) {
return calc_centroid(to.first, node, tam);
}
}
return node;
}
int _K;
void change(int node, int p, int w, int t, int type) {
if (w > _K) return;
if (type == 0) dist[w] = min (dist[w], t);
else dist[w] = 1e9;
for (auto to : g[node]) {
if (!del[to.first] && to.first != p) {
change(to.first, node, w + to.second, t + 1, type);
}
}
}
void solve(int node, int p, int w, int t) {
if (w > _K) return;
ans = min (ans, t + dist[_K - w]);
for (auto to : g[node]) {
if (!del[to.first] && to.first != p) {
solve(to.first, node, w + to.second, t + 1);
}
}
}
void decompose(int node = 0) {
const int centroid = calc_centroid(node, -1, calc_sub(node, -1));
del[centroid] = true;
dist[0] = 0;
for (auto to : g[centroid]) {
if (del[to.first]) continue;
solve(to.first, -1, to.second, 1);
change(to.first, -1, to.second, 1, 0);
}
for (auto to : g[centroid]) {
if (del[to.first]) continue;
change(to.first, -1, to.second, 1, 1);
}
for (auto to : g[centroid]) {
if (del[to.first]) continue;
decompose(to.first);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
_K = K;
for (int i = 0; i < N - 1; i++) {
int st = H[i][0];
int et = H[i][1];
int w = L[i];
g[st].emplace_back(et, w);
g[et].emplace_back(st, w);
}
decompose();
return (ans > 1e8 ? -1 : ans);
}
