#include "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
const int lim = 2e5 + 5;
const int LIM = 1e6 + 5;
const int INF = 1e9;
vector<pair<int, int>>e[lim];
vector<int>g[lim];
int n, k, ans = INT_MAX, h[lim], up[lim][18], cnt[lim], value[LIM];
bitset<lim>in_centroid;
ll f[lim];
void dfs(int s, int p = -1){
cnt[s] = 1;
for(auto& [d, w] : e[s]){
if(d != p){
f[d] = f[up[d][0] = s] + w;
h[d] = h[s] + 1;
for(int i = 1; i < 18; i++){
up[d][i] = up[up[d][i - 1]][i - 1];
}
dfs(d, s);
}
}
}
int lca(int u, int v){
if(h[u] < h[v]){
swap(u, v);
}
int k = h[u] - h[v];
while(k > 0){
int x = __builtin_ctz(k);
u = up[u][x];
k ^= 1 << x;
}
if(u == v){
return u;
}
for(int i = 17; i > -1; i--){
int U = up[u][i], V = up[v][i];
if(U != V){
u = U;
v = V;
}
}
return up[u][0];
}
ll get_distance(int u, int v){
return f[u] + f[v] - (f[lca(u, v)] << 1);
}
int get_distance_height(int u, int v){
return h[u] + h[v] - (h[lca(u, v)] << 1);
}
void build_cnt(int s, int p = -1){
cnt[s] = 1;
for(auto& [d, w] : e[s]){
if(d != p && !in_centroid.test(d)){
build_cnt(d, s);
cnt[s] += cnt[d];
}
}
}
int get_centroid(int s, int n, int p = -1){
for(auto& [d, w] : e[s]){
if(d != p && !in_centroid.test(d) && cnt[d] > (n >> 1)){
return get_centroid(d, n, s);
}
}
return s;
}
int centroid_decomposition(int s, int p = -1){
build_cnt(s, p);
int centroid = get_centroid(s, cnt[s], p);
in_centroid.set(centroid);
for(auto& [d, w] : e[centroid]){
if(!in_centroid.test(d)){
g[centroid].emplace_back(centroid_decomposition(d, centroid));
}
}
return centroid;
}
vector<int>vertex;
void dfs_centroid_support(int root, int s, bool is_add){
ll D = get_distance(root, s);
if(D <= k){
if(is_add){
vertex.emplace_back(s);
}
else{
value[D] = INF;
}
}
for(int& d : g[s]){
dfs_centroid_support(root, d, is_add);
}
}
void dfs_centroid(int s){
value[0] = 0;
for(int& d : g[s]){
vertex.clear();
dfs_centroid_support(s, d, true);
for(int& x : vertex){
minimize(ans, get_distance_height(s, x) + value[k - get_distance(s, x)]);
}
for(int& x : vertex){
minimize(value[get_distance(s, x)], get_distance_height(s, x));
}
}
dfs_centroid_support(s, s, false);
for(int& d : g[s]){
dfs_centroid(d);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
for(int i = 0; i < n; i++){
e[H[i][0]].emplace_back(H[i][1], L[i]);
e[H[i][1]].emplace_back(H[i][0], L[i]);
}
memset(up, h[0] = f[0] = 0, sizeof(up));
dfs(0);
in_centroid.reset();
memset(value, 0x0f, sizeof(value));
dfs_centroid(centroid_decomposition(0));
return ans > n ? -1 : ans;
}
