#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<pll> gmt;
vll lst;
bool used[sz];
ll res = 1e14;
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){
lst.push_back({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;
multiset<pll> gmt;
gmt.insert({0, 0});
for(pii i : g[centroid]){
if(used[i.first]) continue;
calc(i.first, centroid, i.second, 1, centroid);
for(pll i : lst){
auto it = gmt.lower_bound({k - i.first, 0});
if(it != gmt.end() and it -> first == k - i.first){
res = min(res, it -> second + i.second);
}
}
for(pll i : lst){
gmt.insert(i);
}
lst.clear();
}
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);
if(res == 1e14) return -1;
return res;
}
