#include <bits/stdc++.h>
#include "race.h"
using namespace std;
vector<pair<int,int>> g[200010];
map<int,int> mp[200010];
int n,k;
int dis[200010], sum[200010];
int ans = 2e9;
void dfs0(int v, int p = -1)
{
mp[v][sum[v]] = dis[v];
for (auto x : g[v]) if (x.first != p){
dis[x.first] = dis[v] + 1;
sum[x.first] = sum[v] + x.second;
dfs0(x.first, v);
}
}
void dfs(int v, int p = -1)
{
int nowk = k+2*sum[v];
for (auto xx : g[v]){
int x = xx.first;
if (x == p) continue;
dfs(x,v);
if (mp[x].size() > mp[v].size()){
swap(mp[x], mp[v]);
}
for (auto nx : mp[x]){
auto it = mp[v].find(nowk-nx.first);
if (it != mp[v].end()){
ans = min(ans, it->second + nx.second - 2*dis[v]);
}
}
for (auto nx : mp[x]){
auto it = mp[v].find(nx.first);
if (it != mp[v].end()){
mp[v][nx.first] = min(it->second, nx.second);
}
else {
mp[v][nx.first] = nx.second;
}
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for (int i = 0; i < n-1; i++){
int u = H[i][0];
int v = H[i][1];
int w = L[i];
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dfs0(1);
dfs(1);
if (ans == 2e9) ans = -1;
return ans;
}
