#include <bits/stdc++.h>
#include "race.h"
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
const int mxK = 1e6+5;
v<bool> removed;
v<v<pii>> adj;
v<int> sz;
pair<bool, int> a[mxK];
set<pair<int, int>> L;
int ans;
int k;
int dfs(int n, int p) {
sz[n] = 1;
for (auto x : adj[n]) {
if (x.first == p || removed[x.first]) continue;
sz[n] += dfs(x.first, n);
}
return sz[n];
}
int centroid(int u, int p, int n) {
for (auto x : adj[u]) {
if (x.first == p || removed[x.first]) continue;
else if (sz[x.first]*2 >n) return centroid(x.first, u, n);
}
return u;
}
void dfs1(int n, int p, int w, int d) {
L.insert({w, d});
for (auto x : adj[n]) {
if (x.first == p || removed[x.first]) continue;
if (w+x.second > k) continue;
dfs1(x.first, n, w+x.second, d+1);
}
}
void build(int u, int p) {
int n = dfs(u, p);
int c = centroid(u, p, n);
rep(i, 0, mxK) {
a[i] = {false, 1e9};
}
a[0] = {true, 0};
for (auto x : adj[c]) {
if (x.first == p || removed[x.first]) continue;
L.clear();
dfs1(x.first, c, x.second, 1);
for (auto y : L) {
if (y.first > k) continue;
if (a[k-y.first].first == true) {
ans = min(ans, y.second + a[k-y.first].second);
}
}
for (auto y : L) {
a[y.first] = {true, min(a[y.first].second, y.second)};
}
}
removed[c] = true;
for (auto x : adj[c]) {
if (removed[x.first] || x.first == p) continue;
build(x.first, c);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
int n = N;
k = K;
adj.resize(n);
removed.assign(n, false);
sz.resize(n);
rep(i, 0, n-1) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
ans = 1e9;
build(0, -1);
return (ans == 1e9 ? -1 : ans);
}
