#ifndef NOTSUBMIT
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#endif NOTSUBMIT
typedef long long ll;
typedef pair<ll, ll> pll;
#define fr first
#define sc second
vector<pll> adj[200020];
bool chk[200020];
int sz[200020];
int dp[1000020];
vector<pll> v;
void siz(int now, int par){
//cout << "SIZ " << now << endl;
sz[now] = 1;
for (pll p : adj[now]){
int nxt = p.fr;
if (nxt == par || chk[nxt]){ continue; }
siz(nxt, now);
sz[now] += sz[nxt];
}
}
int cen(int now, int par){
//cout << "CEN " << now << endl;
siz(now, par);
int n = sz[now];
while (1){
bool flg = 1;
for (pll p : adj[now]){
int nxt = p.fr;
//cout << "p " << nxt << endl;
if (nxt == par || chk[nxt]){ continue; }
if (2*sz[nxt] > n){ par = now; now = nxt; flg = 0; break; }
}
if (flg){ return now; }
}
}
void g(int now, int par, int dep, ll dis){
//cout << "G " << now << endl;
v.push_back({dep, dis});
for (pll p : adj[now]){
int nxt = p.fr; ll dst = p.sc;
if (nxt == par || chk[nxt]){ continue; }
g(nxt, now, dep+1, dis+dst);
}
}
int ans = 1e9;
void f(int now, int par, ll k){
//cout << "F " << now << ' ' << par << endl;
now = cen(now, par);
//cout << "cen " << now << endl;
memset(dp, -1, sizeof(dp));
for (pll p : adj[now]){
int nxt = p.fr; ll dis = p.sc;
g(nxt, now, 1, dis);
for (pll q : v){
int dep = q.fr; ll val = q.sc;
//cout << "DP " << dep << ' ' << val << endl;
if (k-val >= 0 && dp[k-val] != -1){
//cout << "ans " << dep << ' ' << val << ' ' << dp[k-val] << endl;
ans = min(ans, dep + dp[k-val]);
}
}
for (pll q : v){
int dep = q.fr; ll val = q.sc;
if (val <= k){
if (dp[val] == -1){ dp[val] = dep; }
else{ dp[val] = min(dp[val], dep); }
}
}
v.clear();
}
chk[now] = 1;
for (pll p : adj[now]){
int nxt = p.fr;
if (chk[nxt]){ continue; }
f(nxt, now, k);
}
}
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] });
}
f(0, -1, K);
if (ans == 1e9){ return -1; }
else{ return ans; }
}
