#include "race.h"
#include <bits/stdc++.h>
#define int long long int
#define all(x) x.begin(), x.end()
#define send ios_base::sync_with_stdio(false);
#define help cin.tie(NULL)
#define inf (int)(1e17+1)
#define mod (int)(1e9+7)
#define N (int)(2e5+5)
#define fi first
#define se second
#define endl "\n"
#define double long double
#define eps (double)(1e-9)
#define sa cout<<"sa"<<endl
using namespace std;
int n,k;
vector <pair<int,int>> adj[N];
vector <int> sz(N);
vector <bool> mrk(N);
int sdfs(int c,int pre=0){
sz[c]=1;
for(auto x:adj[c]){
if(x.fi==pre||mrk[x.fi]) continue;
sz[c]+=sdfs(x.fi,c);
}
return sz[c];
}
int get(int c,int pre,int s){
for(auto x:adj[c]){
if(x.fi==pre||mrk[x.fi]) continue;
if(2*sz[x.fi]>s) return get(x.fi,c,s);
}
return c;
}
map <int,int> cmp;
void dfs(int c,int pre,int d,int cur){
if(cur>k) return;
for(auto x:adj[c]){
if(x.fi==pre||mrk[x.fi]) continue;
dfs(x.fi,c,d+1,cur+x.se);
}
cmp[cur]=d;
}
int ans=inf;
void centroid(int c){
c=get(c,0,sdfs(c));
mrk[c]=1;
map<int,int> mp;
mp[0]=0;
for(auto x:adj[c]) if(!mrk[x.fi]){
dfs(x.fi,c,1,x.se);
if(mp.size()<cmp.size()) swap(mp,cmp);
for(auto e:cmp) if(mp.count(k-e.fi)) ans=min(ans,e.se+mp[k-e.fi]);
for(auto e:cmp){
if(mp.count(e.fi)) mp[e.fi]=min(mp[e.fi],e.se);
else mp[e.fi]=e.se;
}
cmp.clear();
}
for(auto x:adj[c]) if(!mrk[x.fi]) centroid(x.fi);
}
int32_t best_path(int32_t Na, int32_t Ka, int32_t H[][2], int32_t L[]){
n=Na;k=Ka;
for(int i=0;i<n-1;i++){
int u=H[i][0],v=H[i][1],w=L[i];
++u;++v;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
centroid(1);
return((ans!=inf)?ans:-1);
}
