#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_bacK
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const ll maxn=2e5+5;
int n=0;
set<pair<int,int> >adj[maxn];
vector<ll>sz(maxn),d(maxn);
void calc(int x,int p){
n++;
sz[x]=1;
for(auto [y,w]:adj[x]){
if(y!=p){
calc(y,x);
sz[x]+=sz[y];
}
}
}
int centroid(int x,int p){
for(auto [y,w]:adj[x]){
if(y==p) continue;
if(sz[y]*2>n) return centroid(y,x);
}
return x;
}
void calc_dist(int x,int p){
for(auto [y,w]:adj[x]){
if(y!=p){
d[y]=d[x]+w;
calc_dist(y,x);
}
}
}
int best_path(int N,int K,int H[][2],int L[]){
for(int i=0;i<N-1;i++){
adj[H[i][0]].insert({H[i][1],L[i]});
adj[H[i][1]].insert({H[i][0],L[i]});
}
int ans=1e9;
queue<int>q;
q.push(0);
while(!q.empty()){
int x=q.front();
q.pop();
n=0;
calc(x,-1);
int root=centroid(x,-1);
map<ll,int>dist;
map<ll,int>cur,clr;
vector<pair<int,int>>v;
function <void(int,int,int)> dfs=[&](int x,int p,int depth){
if(cur[d[x]]==0){
cur[d[x]]=depth;
}
else{
cur[d[x]]=min(cur[d[x]],depth);
}
for(auto [y,w]:adj[x]){
if(y!=p){
d[y]=d[x]+w;
dfs(y,x,depth+1);
}
}
};
for(auto [y,w]:adj[root]){
cur=clr;
d[y]=w;
dfs(y,root,1);
for(auto [i,val]:cur){
if(i==K){
if(val>0){
ans=min(ans,val);
}
}
else if(i<K){
if(val>0&&dist[K-i]>0){
ans=min(ans,val+dist[K-i]);
}
}
}
for(auto [i,val]:cur){
if(dist[i]==0){
dist[i]=val;
}
else if(val>0){
dist[i]=min(dist[i],val);
}
}
}
for(auto [y,w]:adj[root]){
adj[y].erase({root,w});
q.push(y);
}
adj[root].clear();
}
if(ans==1e9) ans=-1;
return ans;
}
