#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 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 = 1e6 + 5;
int n, k, res = 1e9, dp[sz], best[sz];
bool used[sz];
vii g[sz];
vii v, vv;
void dfs(int node, int par){
dp[node] = 1;
for(pii i : g[node]){
if(i.first == par or used[i.first]) continue;
dfs(i.first, node);
dp[node] += dp[i.first];
}
}
int find_centroid(int node, int par, int tsz){
for(pii i : g[node]){
if(i.first == par or used[i.first]) continue;
if(dp[i.first] > tsz / 2) return find_centroid(i.first, node, tsz);
}
return node;
}
void calc(int node, int par, int dis, int h){
if(dis > k) return;
v.push_back({dis, h});
for(pii i : g[node]){
if(i.first == par or used[i.first]) continue;
calc(i.first, node, dis + i.second, h + 1);
}
}
void build(int node){
dfs(node, node);
int centroid = find_centroid(node, node, dp[node]);
for(pii i : g[centroid]){
if(used[i.first]) continue;
v.clear();
calc(i.first, centroid, i.second, 1);
for(pii j : v){
// cout << node << " " << i.first << " " << i.second << " : " << best[k - j.first] << " " << j.first << " " << j.second << endl;
res = min(res, best[k - j.first] + j.second);
vv.push_back(j);
}
for(pii j : v){
best[j.first] = min(best[j.first], j.second);
}
}
for(pii i : vv){
best[i.first] = 1e9;
}
vv.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; i++){
if(H[i][0] == H[i][1]) continue;
g[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
g[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
// cout << "edge : " << H[i][0] << " " << H[i][1] << endl;
}
for(int i = 1; i <= k; i++) best[i] = 1e9;
best[0] = 0;
build(1);
if(res == 1e9) res = -1;
return res;
}
