#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef evenvalue
#include "debug.h"
#else
#define debug(...)
#endif
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
class TreeAnc {
const int n;
const vector<vector<int>> g;
vector<vector<int>> st;
vector<int> tin;
vector<int> tout;
int lg;
int dfs(const int x, const int p = -1, int time = 0) {
tin[x] = time++;
st[x][0] = p;
for (const int y : g[x]) {
if (y == p) continue;
time = dfs(y, x, time);
}
tout[x] = time++;
return time;
}
public:
explicit TreeAnc(const vector<vector<int>> &g, const int root = 0) : g(g), n(g.size()), tin(n), tout(n), lg(ceil(log2(n))) {
st.assign(n, vector<int>(lg + 1));
dfs(root);
for (int j = 1; j <= lg; j++) {
for (int i = 0; i < n; i++) {
const int anc = st[i][j - 1];
st[i][j] = anc == -1 ? -1 : st[anc][j - 1];
}
}
}
bool is_anc(const int x, const int y) {
return (tin[x] <= tin[y]) and (tout[x] >= tout[y]);
}
int lca(int x, const int y) {
if (is_anc(x, y)) return x;
if (is_anc(y, x)) return y;
for (int j = lg; j >= 0; j--) {
const int anc = st[x][j];
if (anc != -1 and not is_anc(anc, y)) {
x = anc;
}
}
return st[x][0];
}
};
class CentroidDecomposition {
const int n;
vector<vector<int>> g;
vector<int> parent;
vector<int> sz;
vector<bool> decomposed;
int subtree_size(const int x, const int p) {
sz[x] = 1;
for (const int y : g[x]) {
if (decomposed[y] or y == p) continue;
sz[x] += subtree_size(y, x);
}
return sz[x];
}
int centroid(const int x, const int p, const int size) {
int c = x;
for (const int y : g[x]) {
if (decomposed[y] or y == p) continue;
if (2 * sz[y] < size) continue;
c = centroid(y, x, size);
break;
}
return c;
}
void decompose(int x, const int p) {
subtree_size(x, p);
x = centroid(x, p, sz[x]);
parent[x] = p;
decomposed[x] = true;
for (const int y : g[x]) {
if (decomposed[y]) continue;
decompose(y, x);
}
}
public:
explicit CentroidDecomposition(const vector<vector<int>> &t) : n(t.size()), g(t) {
parent.assign(n, -2);
decomposed.assign(n, false);
sz.assign(n, 0);
decompose(0, -1);
}
int operator[](const int x) {
return parent[x];
}
};
struct edge {
int x;
int y;
int w;
};
int best_path(const int n, const int K, int H[][2], int L[]) {
vector<edge> edges(n - 1);
for (int i = 0; i < n - 1; i++) {
edges[i].x = H[i][0];
edges[i].y = H[i][1];
edges[i].w = L[i];
}
vector<vector<pair<int, int>>> g(n);
vector<vector<int>> _g(n);
for (const auto [x, y, w] : edges) {
g[x].emplace_back(y, w);
g[y].emplace_back(x, w);
_g[x].push_back(y);
_g[y].push_back(x);
}
TreeAnc tree(_g);
CentroidDecomposition cd(_g);
for (int x = 0; x < n; x++) {
debug(x, cd[x]);
}
vector<int> depth(n);
vector<int64> cost(n);
function<void(int, int, int, int64)> dfs = [&](const int x, const int p, const int d, const int64 c) {
depth[x] = d;
cost[x] = c;
for (const auto [y, w] : g[x]) {
if (y == p) continue;
dfs(y, x, d + 1, c + w);
}
};
dfs(0, -1, 0, 0);
auto dist = [&](const int x, const int y) {
return depth[x] + depth[y] - 2 * depth[tree.lca(x, y)];
};
auto weight = [&](const int x, const int y) {
return cost[x] + cost[y] - 2 * cost[tree.lca(x, y)];
};
int root = -1;
vector<vector<int>> t(n);
for (int x = 0; x < n; x++) {
if (cd[x] == -1) {
root = x;
continue;
}
t[cd[x]].emplace_back(x);
}
int ans = kInf;
function<vector<int>(int)> dfs2 = [&](const int x) {
map<int64, int> path;
path[0] = 0;
vector<int> nodes = {x};
for (const int y : t[x]) {
const vector<int> child = dfs2(y);
for (const int z : child) {
const int64 w = weight(x, z);
const int d = dist(x, z);
if (path.count(K - w)) {
ans = min(ans, path[K - w] + d);
}
}
for (const int z : child) {
const int64 w = weight(x, z);
const int d = dist(x, z);
path.try_emplace(w, d);
path[w] = min(path[w], d);
nodes.push_back(z);
}
}
return nodes;
};
dfs2(root);
return (ans == kInf ? -1 : ans);
}
