#include "race.h"
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x) long long
#define here cerr<<"---------------------------\n"
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define maxn 200005
vector<pll> g[maxn];
ll n,k,c;
bool vis[maxn];
ll ans = llinf;
ll dfs_siz(ll u,ll par){
ll siz = 1;
for(pll p : g[u]){
ll v = p.fi;
if(vis[v]||v==par) continue;
siz+=dfs_siz(v,u);
}
return siz;
}
ll decomp(ll u,ll par,ll m){
ll siz = 1;
bool ok = 1;
for(pll p : g[u]){
ll v = p.fi;
if(vis[v]||v==par) continue;
ll e = decomp(v,u,m);
if(e>m/2) ok = 0;
siz+=e;
}
if(siz<m/2) ok = 0;
if(ok) c = u;
return siz;
}
void dfs(ll u,ll par,ll len,ll j){
if(len==k) ans = min(ans,j);
if(len>=k) return;
for(pll p : g[u]){
ll v = p.fi;
ll w = p.sc;
if(vis[v]||v==par) continue;
dfs(v,u,len+w,j+1);
}
}
map<ll,ll> cnt;
vector<pll> tmp;
void calc(ll u,ll par,ll len,ll j){
if(len>k) return;
if(cnt.find(k-len)!=cnt.end()) ans = min(ans,cnt[k-len]+j);
tmp.pb({len,j});
for(pll p : g[u]){
ll v = p.fi;
ll w = p.sc;
if(vis[v]||v==par) continue;
calc(v,u,len+w,j+1);
}
}
void solve(ll u){
decomp(u,u,dfs_siz(u,u));
//cerr<<u<< " "<<c<<endl;
dfs(c,c,0,0);
vis[c] = 1;
cnt.clear();
for(pll p : g[c]){
ll v = p.fi;
ll w = p.sc;
if(vis[v]) continue;
calc(v,v,w,1);
while(!tmp.empty()){
ll id = tmp.back().fi;
ll len = tmp.back().sc;
tmp.popb();
if(cnt.find(id)==cnt.end()) cnt[id] = len;
else cnt[id] = min(cnt[id],len);
}
}
ll r = c;
for(pll p : g[r]){
ll v = p.fi;
if(vis[v]) continue;
solve(v);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for(ll i = 1;i<=n-1;i++){
ll x = H[i-1][0],y = H[i-1][1],w = L[i-1];
x++;
y++;
g[x].pb({y,w});
g[y].pb({x,w});
}
solve(1);
if(ans==llinf) ans = -1;
return ans;
}
