#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e5+4;
vector <bool> vis;
vector <map <ll, ll>> f;
vector <ll> dep_points, dep_len;
ll sol = maxn;
void dfs_dep(ll c, vector <pair<ll, ll>> g[]){
vis[c] = 1;
for (auto x : g[c]){
if (vis[x.first])continue;
dep_points[x.first] = dep_points[c]+1;
dep_len[x.first] = dep_len[c]+x.second;
dfs_dep(x.first, g);
}
vis[c] = 0;
}
void compare_merge(map <ll, ll> &x, map <ll, ll> &y, ll add, ll c, ll k){
if (x.size() > y.size())swap(x, y);
for (auto it = x.begin(); it != x.end(); it++){
if (k+add-(it->first) < 0)break;
if (!y.count(k+add-(it->first)))continue;
ll v = (it->first);
sol = min(sol, x[v]+y[k+add-v]-2*dep_points[c]);
}
for (auto it = x.begin(); it != x.end(); it++){
if (!y.count(it->first))y[it->first] = (it->second);
else y[it->first] = min(y[it->first], it->second);
}
x.clear();
}
void dfs_solve(ll c, vector <pair<ll, ll>> g[], ll k){
vis[c] = 1;
for (auto x : g[c]){
if (vis[x.first])continue;
dfs_solve(x.first, g, k);
compare_merge(f[x.first], f[c], 2*dep_len[c], c, k);
}
f[c][dep_len[c]] = dep_points[c];
if (f[c].count(k+dep_len[c]))sol = min(sol, f[c][k+dep_len[c]]-dep_points[c]);
}
int best_path(int N, int K, int H[][2], int L[]){
ll n = N, k = K;
vector <pair<ll, ll>> g[n];
vis.resize(n, 0);
for (int i = 0; i < n-1; i++){
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
f.resize(n);
dep_len.resize(n, 0);
dep_points.resize(n, 0);
dfs_dep(0, g);
dfs_solve(0, g, k);
if (sol == maxn)return -1;
else return sol;
}
