#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);
int rng() {
return ui(mrand);
}
int best_path(int n,int k,int ed[][2],int w[]) {
vector<vector<pair<int,int>>> adj(n);
for (int i=0;i<n-1;i++) {
adj[ed[i][0]].emplace_back(ed[i][1],w[i]);
adj[ed[i][1]].emplace_back(ed[i][0],w[i]);
}
vector<ll> depth(n);
vector<int> depth2(n);
auto dfs2=[&](auto &self,int u,int p)->void {
for (auto &[v,w]: adj[u]) if (v!=p) {
depth[v]=depth[u]+w;
depth2[v]=depth2[u]+1;
self(self,v,u);
}
};
dfs2(dfs2,0,-1);
vector<map<ll,int>> S(n);
int ans=1<<30;
auto dfs = [&](auto &self,int u,int p) -> void {
S[u][depth[u]]=depth2[u];
for (auto &[v,w]: adj[u]) if (v!=p) {
self(self,v,u);
if (S[v].size()>S[u].size()) swap(S[u],S[v]);
// depth[a]+depth[b]-2*depth[u]=k
// depth[b]=2*depth[u]+k-depth[a]
for (auto &[other_depth,min_dep]: S[v]) {
if (S[u].count(depth[u]*2+k-other_depth))
cmin(ans,S[u][depth[u]*2+k-other_depth]+min_dep-2*depth2[u]);
}
for (auto &[other_depth,min_dep]: S[v]) {
if (S[u].count(other_depth))
cmin(S[u][other_depth],min_dep);
else
S[u][other_depth]=min_dep;
}
}
// cout << "node " << u + 1 << endl;
// for (auto &[other_dep,min_dep]: S[u]) {
// cout << other_dep << " " << min_dep << endl;
// }
};
dfs(dfs,0,-1);
return (ans==1<<30?-1:ans);
}
