#include "bits/stdc++.h"
#include "race.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
#define endl '\n'
#define pb push_back
#define eb emplace_back
// #define mp make_pair
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
// #define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define rev(i, a, b) for (int i = (a); i >= (b); --i)
const ll inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 5;
void my_assert(int e) {if (!e) abort();}
void fast_io() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
ll power(ll a, ll b, ll m = mod) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << endl;
#else
#define debug(x)
#endif
void calcsz(int nd, int p, int weight, vector<vector<pii>> &adj, vector<int> &sz, vector<int> &lvl, vector<ll> &pref, vector<int> &nodes, vector<pii> &sf) {
lvl[nd] = lvl[p] + 1;
sz[nd] = 1;
pref[nd] = pref[p] + weight;
sf[nd].ff = nodes.size();
nodes.pb(nd);
for (pii &v: adj[nd]) {
if (v.ff != p) {
calcsz(v.ff, nd, v.ss, adj, sz, lvl, pref, nodes, sf);
sz[nd] += sz[v.ff];
}
}
sf[nd].ss = nodes.size();
}
void dfs(int k, int nd, int p, vector<vector<pii>> &adj, vector<int> &sz, vector<int> &lvl, vector<ll> &pref, vector<int> &nodes, vector<pii> &sf, vector<map<ll, int>*> &mp, int &ans) {
int big_child = -1, mxsz = 0;
for (pii &v: adj[nd]) {
if (v.ff != p) {
dfs(k, v.ff, nd, adj, sz, lvl, pref, nodes, sf, mp, ans);
if (mxsz < sz[v.ff]) big_child = v.ff, mxsz = sz[v.ff];
}
}
if (big_child != -1) {
mp[nd] = mp[big_child];
} else {
mp[nd] = new map<ll, int>();
}
for (pii &v: adj[nd]) {
if (v.ff != p && v.ff != big_child) {
map<ll, int> temp;
for (int i = sf[v.ff].ff; i < sf[v.ff].ss; i++) {
if (mp[nd]->find(0ll+k + 2*pref[nd] - pref[nodes[i]]) != mp[nd]->end()) {
ans = min(ans, lvl[nodes[i]] + (*mp[nd])[0ll+k + 2 * pref[nd] - pref[nodes[i]]] - 2 * lvl[nd]);
}
if (temp.find(pref[nodes[i]]) != temp.end()) temp[pref[nodes[i]]] = min(temp[pref[nodes[i]]], lvl[nodes[i]]);
else temp[pref[nodes[i]]] = lvl[nodes[i]];
}
for (auto &j: temp) {
if (mp[nd]->find(j.ff) != mp[nd]->end()) (*mp[nd])[j.ff] = min((*mp[nd])[j.ff], j.ss);
else (*mp[nd])[j.ff] = j.ss;
}
}
}
if (mp[nd]->find(0ll+k + pref[nd]) != mp[nd]->end())
ans = min(ans, (*mp[nd])[0ll+k + pref[nd]] - lvl[nd]);
if (mp[nd]->find(pref[nd]) != mp[nd]->end()) (*mp[nd])[pref[nd]] = min((*mp[nd])[pref[nd]], lvl[nd]);
else (*mp[nd])[pref[nd]] = lvl[nd];
// cout << nd << '\n';
// for (auto &j: (*mp[nd])) {
// cout << j.ff << ' ' << j.ss << '\n';
// }
}
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<pii>> adj(N);
for (int i = 0; i < N; i++) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
vector<int> sz(N), lvl(N), nodes;
vector<pii> sf(N);
vector<ll> pref(N);
vector<map<ll, int>*> mp(N);
int ans = mod;
calcsz(0, 0, 0, adj, sz, lvl, pref, nodes, sf);
dfs(K, 0, 0, adj, sz, lvl, pref, nodes, sf, mp, ans);
if (ans == mod) return -1;
return ans;
}
