#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
const int MAXN = 2e5;
const int MAXK = 1e6 + 1;
vector<pair<ll, ll> > g[MAXN];
vector<ll>* vec[MAXN];
ll sz[MAXN], big[MAXN];
//map<ll, ll> cnt[MAXK];
map<ll, map<ll, ll> > cnt;
ll dep[MAXN];
ll d[MAXN];
void sizes(ll v, ll p, ll depth = 0, ll dist = 0)
{
dep[v] = depth;
d[v] = dist;
sz[v] = 1;
ll b = -1, mx = 0;
for (auto& [u, w]: g[v])
{
if (u != p)
{
sizes(u, v, depth + 1, dist + w);
sz[v] += sz[u];
if (sz[u] > mx)
{
mx = sz[u];
b = u;
}
}
}
big[v] = b;
}
ll ans = 1e9, k, n;
void dfs(ll v, ll p, bool keep = 0)
{
for (auto& [u, w] : g[v])
{
if (u != p && u != big[v])
{
dfs(u, v, 0);
}
}
if (big[v] != -1)
{
dfs(big[v], v, 1);
vec[v] = vec[big[v]];
}
else
{
vec[v] = new vector<ll>();
}
vec[v]->push_back(v);
ll y = k + d[v];
if (cnt.count(y) && cnt[y].size() > 0 && cnt[y].begin()->first - dep[v] < ans)
{
ans = cnt[y].begin()->first - dep[v];
}
cnt[d[v]][dep[v]]++;
for (auto& [u, w] : g[v])
{
if (u != p && u != big[v])
{
for (auto& w : *vec[u])
{
ll x = k * 1ll + 2 * 1ll * d[v] - d[w];
if (cnt.count(x) && cnt[x].size() > 0)
{
ll cur = cnt[x].begin()->first + dep[w];
if (cur - 2 * 1ll * dep[v] < ans)
{
ans = cur - 2 * 1ll * dep[v];
}
}
vec[v]->push_back(w);
}
for (auto& w : *vec[u])
cnt[d[w]][dep[w]]++;
}
}
if (!keep)
{
for (auto& u : *vec[v])
{
cnt[d[u]][dep[u]]--;
if (cnt[d[u]][dep[u]] == 0)
cnt[d[u]].erase(dep[u]);
if (cnt[d[u]].empty())
cnt.erase(d[u]);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K;
for (int i = 0; i < n - 1; i++)
{
int x = H[i][0], y = H[i][1], z = L[i];
g[x].push_back({y, z});
g[y].push_back({x, z});
}
sizes(0, 0);
dfs(0, 0);
return (ans == 1e9 ? -1 :ans);
}
/*
4 3
0 1 1
1 2 2
1 3 4
2
*/
