#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2e5 + 5;
vector<pair<int,int>> adj[N];
int sz[N];
int depth[N];
int md[10 * N];
i64 dist[N];
bool vis[N];
int k;
int ans = N + 1;
void find_size(int u,int p){
sz[u] = 1;
for(auto [v,w] : adj[u]){
if(vis[v] || v == p) continue;
find_size(v,u);
sz[u] += sz[v];
}
}
// Find Centeroid of the subtree of u
int findC(int u,int p,int S){
for(auto [v,w] : adj[u]){
if(vis[v] || v == p) continue;
if(sz[v] > S / 2){
return findC(v,u,S);
}
}
return u;
}
vector<pair<i64,int>> ad;
vector<int> rem;
void dfs(int u,int p){
vector<vector<pair<i64,int>>> all;
for(auto [v,w] : adj[u]){
if(v == p || vis[v]) continue;
depth[v] = depth[u] + 1;
dist[v] = dist[u] + w;
ad.emplace_back(dist[v],depth[v]);
dfs(v,u);
if(p == -1){
all.push_back(ad);
ad.clear();
}
}
if(p != -1) return;
for(auto &vec : all){
for(auto [w,d] : vec){
if(w <= k){
ans = min(ans,d + md[k - w]);
}
}
for(auto [w,d] : vec){
md[w] = min(md[w],d);
rem.push_back(w);
}
}
}
// Initialize the subtree of u based on the array vis
void init(int u,int p){
find_size(u,p);
int C = findC(u,p,sz[u]);
vis[C] = true;
ad.clear();
depth[C] = 0;
dist[C] = 0;
md[0] = 0;
for(int &w : rem){
md[w] = N + 1;
}
rem.clear();
dfs(C,-1);
for(auto [v,w] : adj[C]){
if(vis[v]) continue;
init(v,C);
}
}
int best_path(int n,int K,int H[][2],int L[]){
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]);
}
k = K;
for(int i = 0;i<N;i++){
md[i] = N + 1;
}
init(0,-1);
return (ans > n ? -1 : ans);
}
