#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define MAXN 200200
vector<pair<int, int>> adj[MAXN];
using ll = long long;
ll bonus[MAXN];
int sti[MAXN];
unordered_map<ll, int> mp[MAXN];
int ans=1e9;
ll k;
void dfs(int v, int p, int d) {
int id=-1;
for(auto e : adj[v]) {
int u=e.first, w=e.second;
if(u==p) continue;
dfs(u, v, d+1);
if(id<0||mp[sti[u]].size()>mp[id].size()) {
id=sti[u];
bonus[v]=bonus[u]+w;
}
}
if(id<0) {
id=v;
bonus[v]=0LL;
}
for(auto e : adj[v]) {
int u=e.first, w=e.second;
if(u==p||sti[u]==id) continue;
for(auto pr : mp[sti[u]]) {
ll cur=pr.first+w+bonus[u];
auto p = mp[id].find(k-cur-bonus[v]);
if(p==mp[id].end()) continue;
ans=min(ans, p->second+pr.second-2*d);
}
for(auto pr : mp[sti[u]]) {
ll cur=pr.first+w+bonus[u]-bonus[v];
auto p = mp[id].find(cur);
if(p==mp[id].end()) {
mp[id][cur]=pr.second;
} else {
p->second=min(p->second, pr.second);
}
}
}
auto p2 = mp[id].find(k-bonus[v]);
if(p2!=mp[id].end()) {
ans=min(ans, p2->second-d);
}
mp[id][-bonus[v]]=d;
sti[v]=id;
}
int best_path(int N, int K, int H[][2], int L[])
{
k=K;
for(int i=0;i<N-1;i++) {
int v=H[i][0], u=H[i][1], w=L[i];
adj[v].push_back({u, w});
adj[u].push_back({v, w});
}
dfs(0, -1, 0);
if(ans==1e9) ans=-1;
return ans;
}
