//
// ~oisín~ C++ Template
//
#include <bits/stdc++.h>
#define MX_N 200005
#define mp make_pair
#define mod7 1000000007
#define modpi 314159
#define PI 3.141592653589793238
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a) a.begin(),a.end()
#define fi first
#define se second
#define ll long long int
#define ull unsigned long long int
int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] = {+0, +0, +1, -1};
int dy4[4] = {+1, -1, +0, +0};
ll gcd(ull a, ull b){
return (a==0)?b:gcd(b%a,a);
}
ll lcm(ull a, ull b){
return a*(b/gcd(a,b));
}
const long long INF = 1e18;
using namespace std;
map<ll, bool> d_b;
map<ll, int> d_id;
map<int, int> l_q[MX_N];
ll k;
bool is_heavy[MX_N];
int card[MX_N], p[MX_N], heavy[MX_N], l[MX_N], tin[MX_N], tout[MX_N], whom[MX_N*2];
ll depth[MX_N];
int gl_tit = 0;
int gl_dit = 0;
vector<pair<int, ll> > adj[MX_N];
void info_dfs(int at){
whom[gl_tit] = at;
tin[at] = gl_tit++;
card[at] = 1;
heavy[at] = -1;
is_heavy[at] = false;
for(auto& [to, w] : adj[at]){
if(p[at] == to){
continue;
}
p[to] = at;
l[to] = l[at] + 1;
depth[to] = depth[at] + w;
info_dfs(to);
card[at] += card[to];
if(heavy[at] == -1){
heavy[at] = to;
}else{
if(card[to] > card[heavy[at]]){
heavy[at] = to;
}
}
}
if(heavy[at] != -1){
is_heavy[heavy[at]] = true;
}
whom[gl_tit] = -1;
tout[at] = gl_tit++;
return;
}
int ans = 1000000009;
void dfs(int at){
for(auto& [to, w] : adj[at]){
if(to == p[at] || is_heavy[to]){
continue;
}
dfs(to);
}
if(heavy[at] != -1){
dfs(heavy[at]);
}
for(auto& [to, w] : adj[at]){
if(to == p[at] || is_heavy[to]){
continue;
}
for(int i=tin[to];i<=tout[to];++i){
if(whom[i] == -1){
continue;
}
if(d_b[depth[whom[i]]] == false){
l_q[gl_dit][l[whom[i]]]++;
d_id[depth[whom[i]]] = gl_dit++;
d_b[depth[whom[i]]] = true;
}else{
int tmp_it = d_id[depth[whom[i]]];
l_q[tmp_it][l[whom[i]]]++;
}
}
}
if(d_b[depth[at]] == false){
l_q[gl_dit][l[at]]++;
d_id[depth[at]] = gl_dit++;
d_b[depth[at]] = true;
}else{
int tmp_it = d_id[depth[at]];
l_q[tmp_it][l[at]]++;
}
for(auto& [to, w] : adj[at]){
if(to == p[at] || is_heavy[to]){
continue;
}
for(int i=tin[to];i<=tout[to];++i){
if(whom[i] == -1){
continue;
}
int a = whom[i];
ll db = k + 2ll*depth[at] - depth[a];
if(d_b[db] == false){
continue;
}
int tmp_id = d_id[db];
if(l_q[tmp_id].empty()){
continue;
}
int lb = l_q[tmp_id].begin()->first;
if(((lb == l[a]) && (l_q[tmp_id][lb] == 1) && depth[a] == db) || (l_q[tmp_id][lb] == 0)){
continue;
}
//cout << "With god as my witness, a = " << a << ", db & lb = " << db << " & " << lb << ", giving " << l[a] + lb - 2*l[at] << " length(s)\n";
ans = min(ans, l[a] + lb - 2*l[at]);
}
}
int a = at;
int tmp_id, lb;
ll db = k + 2ll*depth[at] - depth[a];
if(d_b[db] == false){
goto crime;
}
tmp_id = d_id[db];
if(l_q[tmp_id].empty()){
goto crime;
}
lb = l_q[tmp_id].begin()->first;
if(((lb == l[a]) && (l_q[tmp_id][lb] == 1) && depth[a] == db) || (l_q[tmp_id][lb] == 0)){
goto crime;
}
//cout << "With god as my witness, a = " << a << ", db & lb = " << db << " & " << lb << ", giving " << l[a] + lb - 2*l[at] << " length(s)\n";
ans = min(ans, l[a] + lb - 2*l[at]);
crime:
if(!is_heavy[at]){
for(int i=tin[at];i<=tout[at];++i){
if(whom[i] == -1){
continue;
}
int tmp_it = d_id[depth[whom[i]]];
l_q[tmp_it][l[whom[i]]]--;
}
}
return;
}
int best_path(int N, int K, int H[][2], int L[]){
for(int i=0;i<N-1;++i){
int u = H[i][0], v = H[i][1];
ll w = L[i];
adj[u].pb({v, w});
adj[v].pb({u, w});
}
memset(heavy, -1, sizeof(heavy));
k = K;
l[0] = 0;
depth[0] = 0;
info_dfs(0);
dfs(0);
if(ans == 1000000009){
return -1;
}
return ans;
}
