#include "race.h"
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int, int>> ad[200005];
map<int, int> f[200005];
int lazy[200005], lazyans[200005], curans = 1e9, target;
void unite(int u, int v)
{
if(f[u].size() < f[v].size()){
f[u].swap(f[v]);
swap(lazy[u], lazy[v]);
swap(lazyans[u], lazyans[v]);
}
for(pair<int, int> i : f[v]){
i.first += lazy[v]; i.second += lazyans[v];
int targetval = target - i.first - lazy[u];
if(f[u].count(targetval) == 1){
//cerr<<"B"<<u<<" "<<v<<" "<<targetval+lazy[u]<<" "<<i.second<<" "<<lazyans[v]<<" "<<f[u][targetval]<<" "<<lazyans[u]<<endl;
curans = min(curans, i.second + f[u][targetval]+lazyans[u]);
}
}
//cerr<<"BBBBBBBBBB"<<u<<" "<<v<<" "<<lazyans[u]<<" "<<lazyans[v]<<endl;
for(pair<int, int> i : f[v]){
i.first += lazy[v]; i.second += lazyans[v];
i.first -= lazy[u]; i.second -= lazyans[u];
if(f[u].count(i.first) == 0) f[u][i.first] = i.second;
else{
int &val = f[u][i.first];
val = min(val, i.second);
}
}
}
bool visited[200005];
void dfs(int u)
{
visited[u] = 1;
f[u][0] = 0;
for(pair<int, int> i : ad[u]){
int v = i.first, c = i.second;
if(visited[v] == 1) continue;
dfs(v); lazy[v] += c; lazyans[v]++;
unite(u, v);
//cerr<<"A"<<u<<" "<<v<<" "<<c<<" "<<curans<<endl;
}
//cerr<<"A"<<u<<endl;
//for(pair<int, int> i : f[u]) cerr<<i.first+lazy[u]<<" "<<i.second+lazyans[u]<<endl;
visited[u] = 0;
}
int32_t best_path(int32_t n, int32_t k, int32_t H[][2], int32_t L[])
{
target = k;
for(int i = 0; i < n-1; i++){
int u = H[i][0], v = H[i][1], c = L[i];
ad[u].push_back({v, c});
ad[v].push_back({u, c});
}
dfs(1);
if(curans < n) return curans;
else return -1;
}
