#ifndef NOTSUBMIT
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#endif // NOTSUBMIT
typedef long long ll;
typedef pair<ll, ll> pl2;
typedef pair<int, int> pi2;
#define fr first
#define sc second
vector<pl2> adj[100020];
bool chk[100020];
int sz[100020];
int siz(int now, int par){
//cout << " SIZ " << now << ' ' << par << endl;
sz[now] = 1;
for (pl2 p : adj[now]){
//cout << " P " << p.fr << ' ' << p.sc << endl;
int nxt = p.fr;
if (nxt == par || chk[nxt]){ continue; }
//cout << " ?? " << nxt << ' ' << now << endl;
sz[now] += siz(nxt, now);
}
//cout << " SIZE " << now << ' ' << sz[now] << endl;
return sz[now];
}
int cen(int now){
siz(now, -1);
int ptr = now, tar = sz[now] / 2;
int par = -1;
while (1){
bool flg = 1;
for (pl2 p : adj[ptr]){
int nxt = p.fr;
if (par == nxt || chk[nxt] || sz[nxt] <= tar){ continue; }
flg = 0; par = ptr; ptr = nxt; break;
}
if (flg){ return ptr; }
}
}
int k;
vector<pi2> v;
int dp[1000020];
queue<int> q;
void dpf(int now, int par, int dep, ll dis){
if (dis > k){ return; }
v.push_back({dep, dis});
for (pl2 p : adj[now]){
int nxt = p.fr; ll dst = p.sc;
if (par == nxt || chk[nxt]){ continue; }
dpf(nxt, now, dep+1, dis+dst);
}
}
int ans = 1e9;
void f(int now){
int r = cen(now);
//cout << "CEN " << now << ' ' << r << endl;
for (pl2 p : adj[r]){
int nxt = p.fr; ll dis = p.sc;
dpf(nxt, r, 1, dis);
for (pi2 pp : v){
int dep = pp.fr, dst = pp.sc;
q.push(dst);
//cout << "ANS " << dep << ' ' << dst << ' ';
if (dp[k-dst] != -1){ ans = min(ans, dp[k-dst] + dep); }
//cout << ans << endl;
}
for (pi2 pp : v){
int dep = pp.fr, dst = pp.sc;
//cout << "DP " << dst << ' ' << dp[dst] << ' ' << dep << endl;
if (dp[dst] == -1){ dp[dst] = dep; }
else{ dp[dst] = min(dp[dst], dep); }
}
v.clear();
}
while (!q.empty()){ dp[q.front()] = -1; q.pop(); }
chk[r] = 1;
for (pl2 p : adj[r]){
int nxt = p.fr;
if (chk[nxt]){ continue; }
f(nxt);
}
}
int best_path(int N, int K, int H[][2], int L[]){
for (int i = 0; i < N-1; i++){
adj[ H[i][0] ].push_back({ H[i][1], L[i] });
adj[ H[i][1] ].push_back({ H[i][0], L[i] });
}
k = K; memset(dp, -1, sizeof(dp)); dp[0] = 0;
f(0);
if (ans == 1e9){ return -1; }
else{ return ans; }
}
