#include <bits/stdc++.h>
#include "race.h"
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define foru(i, v) for(auto i : v)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
const int maxn = 2e5;
map<ll, int> *cnt[maxn];
int sz[maxn];
int prof[maxn];
ll tam[maxn];
vpii tree[maxn];
int res, k;
void dfs(int u, int p){
int mx = -1, bigchild = -1;
sz[u] = 1;
foru(v, tree[u]){
if(v.fi != p){
prof[v.fi] = prof[u] + 1;
tam[v.fi] = tam[u] + (ll) v.se;
dfs(v.fi, u);
sz[u] += sz[v.fi];
if(sz[v.fi] > mx){
mx = sz[v.fi];
bigchild = v.fi;
}
}
}
cnt[u] = (bigchild == -1) ? new map<ll, int> : cnt[bigchild];
ll distancia;
foru(v, tree[u]){
if(v.fi != p && v.fi != bigchild){
foru(i, *cnt[v.fi]){
distancia = i.fi;
distancia -= tam[u];
if((*cnt[u]).count(tam[u] + ((ll) k - distancia))){
res = (res == -1) ? ((*cnt[u])[tam[u] + ((ll) k - distancia)] - prof[u]) + (i.se - prof[u]) : min(res, ((*cnt[u])[tam[u] + ((ll) k - distancia)] - prof[u]) + (i.se - prof[u]));
}
}
foru(i, *cnt[v.fi]){
if((*cnt[u]).count(i.first)){
(*cnt[u])[i.first] = min((*cnt[u])[i.first], i.second);
continue;
}
(*cnt[u])[i.first] = i.second;
}
}
}
if((*cnt[u]).count((ll) k + tam[u])){
res = (res == -1) ? ((*cnt[u])[tam[u] + (ll) k] - prof[u]) : min(res, ((*cnt[u])[tam[u] + (ll) k] - prof[u]));
}
(*cnt[u])[tam[u]] = prof[u];
}
int best_path(int N, int K, int H[][2], int L[]){
forn(i, 0, N - 2){
tree[H[i][0]].pb(mp(H[i][1], L[i]));
tree[H[i][1]].pb(mp(H[i][0], L[i]));
}
k = K;
res = -1;
dfs(0, 0);
return res;
}
