#include <bits/stdc++.h>
#include "race.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("fast-math")
#pragma GCC target("popcnt")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
using namespace std;
#define ll long long int
const int N = 2e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;
int sz[N];
map<ll, pair<pair<int, int>, pair<int, int>>> mp;
vector<vector<pair<int, int>>> g(N, vector<pair<int, int>> ());
vector<vector<int>*> vec(N), vec1(N);
int dep[N];
int up[N][19];
ll sm[N];
void dfs(int u, int p) {
up[u][0] = p;
for (int i = 1; i <= 18; i++) {
if (up[u][i - 1] != -1) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
}
for (auto v: g[u])
if (v.first != p) {
dep[v.first] = dep[u] + 1;
sm[v.first] = sm[u] + v.second;
dfs(v.first, u);
sz[u] += sz[v.first];
}
}
int lca(int u, int v) {
if (dep[u] > dep[v]) swap(u, v);
int del = dep[v] - dep[u];
for (int msk = 0; msk <= 18; msk++) {
if (del & (1 << msk)) {
v = up[v][msk];
}
}
if (u == v) return u;
for (int i = 18; i >= 0; i--)
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
return up[u][0];
}
int ans = INF, kkk;
void dfs1(int u, int p, bool keep) {
int sz_max = 0, bg = -1;
for (auto v: g[u]) {
if (v.first != p) {
if (sz[v.first] > sz_max) {
sz_max = sz[v.first];
bg = v.first;
}
}
}
for (auto v: g[u]) {
if (v.first != p && v.first != bg) {
dfs1(v.first, u, 0);
}
}
if (bg != -1) {
dfs1(bg, u, 1);
vec[u] = vec[bg];
} else vec[u] = new vector<int> ();
vec[u] -> push_back(u);
if (mp[sm[u]].first.first >= dep[u] || mp[sm[u]].first.second == 0) {
swap(mp[sm[u]].first, mp[sm[u]].second);
mp[sm[u]].first = {dep[u], u};
} else if (mp[sm[u]].second.first >= dep[u] || mp[sm[u]].second.second == 0) {
mp[sm[u]].second = {dep[u], u};
}
for (auto v: g[u]) {
if (v.first != p && v.first != bg) {
for (auto i: *vec[v.first]) {
vec[u] -> push_back(i);
if (sm[i] == sm[up[i][0]]) continue;
if (mp[sm[i]].first.first >= dep[i] || mp[sm[i]].first.second == 0) {
swap(mp[sm[i]].first, mp[sm[i]].second);
mp[sm[i]].first = {dep[i], i};
} else if (mp[sm[i]].second.first >= dep[i] || mp[sm[i]].second.second == 0) {
mp[sm[i]].second = {dep[i], i};
}
ll ss = sm[i] - sm[u];
if (ss > kkk) continue;
ll other = (kkk - ss) + sm[u];
if (mp[other].first.second != 0 && lca(mp[other].first.second, i) == u) {
ans = min(ans, (dep[i] - dep[u]) + (mp[other].first.first - dep[u]));
}
if (mp[other].second.second != 0 && lca(mp[other].second.second, i) == u) {
ans = min(ans, (dep[i] - dep[u]) + (mp[other].second.first - dep[u]));
}
}
}
}
if (mp[sm[u] + kkk].first.second != 0) {
ans = min(ans, mp[sm[u] + kkk].first.first - dep[u]);
// cout << u << " " << sm[u] + kkk << '\n';
}
if (keep == 0)
mp = {};
}
int best_path(int n, int k, int h[][2], int l[]) {
kkk = k;
ans = INF;
for (int i = 1; i <= n; i++) {
sz[i] = 1;
dep[i] = 1;
sm[i] = 0ll;
for (int j = 0; j < 19; j++)
up[i][j] = -1;
}
vec = vec1;
mp = {};
for (int i = 1; i <= n; i++)
g[i].clear();
for (int i = 0; i < (n - 1); i++) {
h[i][0]++, h[i][1]++;
g[h[i][0]].push_back({h[i][1], l[i]});
g[h[i][1]].push_back({h[i][0], l[i]});
}
dfs(1, -1);
dfs1(1, -1, 1);
if (ans == INF) ans = -1;
return ans;
}
// int32_t main(int32_t argc, char *argv[]) {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int T = 1;
// // cin >> T;
// while (T--) {
// int n, k;
// cin >> n >> k;
// int h[n - 1][2], l[n - 1];
// for (int i = 0; i < n - 1; i++)
// cin >> h[i][0] >> h[i][1];
// for (int i = 0; i < n - 1; i++)
// cin >> l[i];
// cout << best_path(n, k, h, l) << '\n';
// }
// return 0;
// }
