#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define int long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cerr << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define FASTIO \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
int n, k;
vector<vector<pll>> al(200005);
int ans = 1e15;
int os[200005];
vector<multiset<pll>> mem(200005);
int depth[200005];
int pd[200005];
void dfs(int x, int p){
multiset<pll> bs, ss;
int bso = 0, sso = 0;
bs.insert({0, depth[x]});
for (pll ed : al[x]){
int it = ed.f;
if (it == p) continue;
dfs(it, x);
}
//cout << "WE ARE AT " << x << endl;
for (pll ed: al[x]){
int it = ed.f;
if (it == p) continue;
ss.swap(mem[it]);
sso = os[it];
if (ss.size() > bs.size()) {
bs.swap(ss);
swap(bso, sso);
}
//dg(x);
//dg(it);
/*cout << "SS : " ;
for (auto it : ss){
cout << "{ " << it.f << ", " << it.s << " } ";
}
cout << endl;
cout << "BS : " ;
for (auto it : bs ){
cout << "{ " << it.f << ", " << it.s << " } ";
}
cout << endl;*/
for (auto cand : ss){
// length, endpoint
int tar = (k - (sso + cand.f)) - bso;
auto itr = bs.lower_bound({tar, -1e15});
if (itr != bs.end() and (*itr).f == tar){
int neu = (*itr).s + cand.s - 2 * depth[x];
if (neu > 0) ans = min(ans, neu);
}
}
for (auto cand : ss){
// add to big set, negating offset
bs.insert({cand.f + sso - bso, cand.s});
}
}
/*cout << "BS AFTER: " ;
for (auto it : bs){
cout << "{ " << it.f << ", " << it.s << " } ";
}
cout << endl;*/
os[x] = bso + pd[x];
mem[x].swap(bs);
}
void ddfs(int x, int p){
for (auto it : al[x]){
if (it.f == p) continue;
depth[it.f] = depth[x] + 1;
pd[it.f] = it.s;
ddfs(it.f, x);
}
}
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[])
{
n = N, k = K;
iloop(0, n-1){
int a = H[i][0], b = H[i][1];
int c = L[i];
al[a].pb({b, c});
al[b].pb({a, c});
}
ddfs(0, -1);
dfs(0, -1);
/*cout << "DEPTH\n";
iloop(0, n) cout << depth[i] << " ";
cout << "PD\n";
iloop(0, n) cout << pd[i] << " ";*/
return (ans == 1e15 ? -1 : ans);
}
