#include "race.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int sz = 2e5 + 5;
vii g[sz];
vii centr[sz];
int n, k, dp[sz];
multiset<pii> mt[sz];
bool used[sz];
void dfs(int node, int par){
dp[node] = 1;
for(pii i : g[node]){
if(used[i.first] or i.first == par) continue;
dfs(i.first, node);
dp[node] += dp[i.first];
}
}
int find_centr(int node, int par, int tsz){
for(pii i : g[node]){
if(used[i.first] or i.first == par) continue;
if(dp[i.first] > tsz / 2) return find_centr(i.first, node, tsz);
}
return node;
}
void calc(int node, int par, ll dis, int h, int centroid){
centr[node].push_back({centroid, h});
if(dis <= k){
mt[centroid].insert({dis, h});
// cout << node << " " << par << " " << dis << " " << h << " " << centroid << endl;
}
for(pii i : g[node]){
if(used[i.first] or i.first == par) continue;
// cout << "go from " << node << " to " << i.first << endl;
calc(i.first, node, dis + i.second, h + 1, centroid);
}
}
void build(int x){
dfs(x, x);
int centroid = find_centr(x, x, dp[x]);
// cout << "new" << endl;
calc(centroid, centroid, 0, 0, centroid);
used[centroid] = true;
for(pii i : g[centroid]){
if(used[i.first]) continue;
build(i.first);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
for(int i = 0; i < n - 1; i++){
H[i][0]++, H[i][1]++;
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
build(1);
int res = 2e9;
for(int i = 1; i <= n; i++){
auto it = mt[i].lower_bound({k, 0});
if(it != mt[i].end() and it -> first == k){
res = min(res, it -> second);
// cout << "aloneboy " << it -> first << " " << it -> second << endl;
}
multiset<pii> tmp = mt[i];
for(pii j : mt[i]){
tmp.erase(tmp.find(j));
auto it = tmp.lower_bound({k - j.first, 0});
if(it != tmp.end() and it -> first == k - j.first){
res = min(res, it -> second + j.second);
// cout << "pair of : " << i << endl;
// cout << j.first << " " << j.second << endl;
// cout << it -> first << " " << it -> second << endl;
// cout << "----------------" << endl;
}
tmp.insert(j);
}
}
if(res == 2e9) return -1;
return res;
}
