#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll , ll> PII ;
typedef vector<bool> vb ;
typedef vector<ll> vi;
typedef vector<PII> vpi;
typedef vector<vector<ll>> vvi;
typedef vector<vector<PII>> vvpi;
typedef vector<char> vc ;
const double EBS = 1e-9;
const double pi = 3.14159265358979 ;
#define Log(x) (31^__builtin_clz(x))
#define logll(x) (63^__builtin_clzll(x))
// processor cycle counter can be used to get a random number easily :)
#define rand __builtin_ia32_rdtsc()
#define popcount(i) __builtin_popcount(i)
#define popcountll(i) __builtin_popcountll(i)
#define mp make_pair
#define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n";
#define testCase ll t; cin >> t; while (t--)
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(f, s, i) for (ll i = f; (int) i < s; i++)
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
#define calunique(v) disance(v.begin(),unique(v.begin(),v.end()));
#define el cout << endl
#define pb push_back
#define no cout << "NO\n"
#define yes cout << "YES\n"
#define all(v) v.begin(), v.end()
#define INF (ll) 1e9
#define INFLL (ll)1e18
#define debug cout << "\n___________________________________\n"
// #define int ll
#define Left ((p << 1) + 1)
#define Right ((p << 1) + 2)
const int N = 2e5 + 9 ;
int K ;
vpi adj[N];
int sum[N] , depth[N] ;
vector< map<int , int> > cnt(N);
int ans = 0 ;
void dfs_depth(int node , int par){
for(auto [nd , w] : adj[node]){
if(nd != par){
depth[nd] = depth[node] + 1 ;
sum[nd] = sum[node] + w ;
dfs_depth(nd , node);
}
}
}
void dfs(int node , int par){
for(auto [nd , w] : adj[node]){
if(nd != par) dfs(nd , node);
}
int target = K + 2 * sum[node];
cnt[node][sum[node]] = depth[node] ;
for(auto [nd , w] : adj[node]){
if(nd != par){
if(cnt[nd].size() > cnt[node].size()) swap(cnt[nd] , cnt[node]);
for(auto [key , val] : cnt[nd]){
int find = target - key ;
/*cout << target << " " << find << " " << key << endl ;*/
if(cnt[node].find(find) != cnt[node].end()){
// debug ;
ans = min(ans , val + cnt[node][find] - 2*depth[node]);
}
}
for(auto [key , val] : cnt[nd]){
if(cnt[node].find(key) != cnt[node].end()){
cnt[node][key] = min(cnt[node][key] , val);
}else{
cnt[node][key] = val ;
}
}
}
}
}
int best_path(int n , int k , int (*edges)[2] , int *weights){
K = k ;
rep(0 , n-1 , i){
auto [u , v] = mp(edges[i][0] , edges[i][1]);
adj[u].pb(mp(v , weights[i]));
adj[v].pb(mp(u , weights[i]));
}
ans = INF ;
dfs_depth(0 , 0);
dfs(0 , 0) ;
if(ans == INF) ans = -1 ;
return ans;
}
