#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef tuple<int, int, int> iii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LSOne(S) ((S) & -(S))
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
int best_path(int n, int K, int edges[][2], int weights[]) {
vector<vii> AL(n);
for (int i = 0; i < n - 1; i++) {
auto [u, v] = edges[i];
int w = weights[i];
AL[u].push_back({v, w});
AL[v].push_back({u, w});
}
int ans = 1e9;
auto dfs = [&](auto self, int u, int p, int d, ll s) -> map<ll, int> {
map<ll, int> res;
res[s] = d;
ll targ = K + 2 * s;
for (auto [v, w] : AL[u]) {
if (v == p) continue;
auto cur = self(self, v, u, d + 1, s + w);
if (res.size() < cur.size()) swap(res, cur);
for (auto [k, v] : cur) {
if (res.count(targ - k)) ckmin(ans, v + res[targ - k] - 2 * d);
}
for (auto [k, v] : cur) {
if (res.count(k))
ckmin(res[k], v);
else
res[k] = v;
}
}
return res;
};
dfs(dfs, 0, -1, 0, 0);
return ans == 1e9 ? -1 : ans;
}
// int main() {
// ios_base::sync_with_stdio(0), cin.tie(0);
// int tc = 1;
// // cin >> tc;
// while (tc--) {
// solve();
// }
// return 0;
// }
