#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
#define f first
#define s second
const int NN = 200000;
const int MX = 1000000;
int n, k, sz[NN];
ll level[NN], ANS = INT_MAX, dist[NN];
map<ll, ll> min_edges;
vector<int> nodes[NN];
vector<pair<int, int>> adj[NN];
void dfs_pre(int x, int pr, int lvl, ll sm) {
sz[x] = 1, level[x] = lvl, dist[x] = sm;
for(auto e : adj[x]) if(e.f != pr) {
dfs_pre(e.f, x, lvl + 1, sm + e.s);
sz[x] += sz[e.f];
}
}
void dfs(int x, int pr, bool keep) {
int mx = 0, big_child = -1;
for(auto e : adj[x])
if(e.f != pr)
if(sz[e.f] > mx) {
mx = sz[e.f];
big_child = e.f;
}
if(big_child == -1) {
nodes[x].push_back(x);
if(keep)
min_edges[dist[x]] = level[x];
return;
}
for(auto e : adj[x])
if(e.f != pr && e.f != big_child)
dfs(e.f, x, false);
dfs(big_child, x, true);
swap(nodes[x], nodes[big_child]);
nodes[x].push_back(x);
if(min_edges.find(dist[x]) == min_edges.end()) min_edges[dist[x]] = level[x];
else min_edges[dist[x]] = min(min_edges[dist[x]], level[x]);
if(min_edges.find(dist[x] + k) != min_edges.end())
ANS = min(ANS, min_edges[dist[x] + k]);
for(auto e : adj[x])
if(e.f != pr && e.f != big_child)
for(auto nd : nodes[e.f]) {
ll d = dist[nd] - dist[x];
int lvl = level[nd] - level[x];
if(d == k) ANS = min(ANS, ll(lvl));
else if(d < k && min_edges.find(k - d + dist[x]) != min_edges.end())
ANS = min(ANS, min_edges[k - d + dist[x]] - level[x] + lvl);
if(min_edges.find(dist[nd]) == min_edges.end()) min_edges[dist[nd]] = level[nd];
else min_edges[dist[nd]] = min(min_edges[dist[x]], level[nd]);
nodes[x].push_back(nd);
}
if(!keep)
for(auto& e : min_edges)
e.s = INT_MAX;
}
int best_path(int _N, int K, int H[][2], int L[]) {
n = _N, k = K;
for(int i = 0;i < n - 1;i ++) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
dfs_pre(0, -1, 0, 0);
dfs(0, -1, true);
return (ANS == INT_MAX ? -1 : ANS);
}
