#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define pb push_back
using namespace std;
typedef pair<int, int> p;
int n, k;
vector<p> g[202020];
vector<int> init;
int sz[202020], use[202020], chk[1010101];
int getSize(int v, int par){
sz[v] = 1;
for(auto i : g[v]){
if(i.x == par || use[i.x]) continue;
sz[v] += getSize(i.x, v);
}
return sz[v];
}
int getCent(int v, int par, int cnt){
for(auto i : g[v]){
if(i.x == par || use[i.x]) continue;
if(sz[i.x] > cnt/2) return getCent(i.x, v, cnt);
}
return v;
}
void update(int now, int prv, int dst, int dep){
if(dst > k) return;
chk[dst] = min(chk[dst], dep);
init.push_back(dst);
for(auto i : g[now]){
if(i.x == prv || use[i.x]) continue;
update(i.x, now, dst + i.y, dep + 1);
}
}
int calc(int now, int prv, int dst, int dep){
int ret = 1e9+7;
if(dst > k) return ret;
if(chk[k-dst] < 1e9){
ret = chk[k-dst] + dep;
}
for(auto i : g[now]){
if(use[i.x] || i.x == prv) continue;
ret = min(ret, calc(i.x, now, dst + i.y, dep + 1));
}
return ret;
}
int solve(int v){
int cnt = getSize(v, -1);
int cent = getCent(v, -1, cnt); use[cent] = 1;
int ret = 1e9+7;
for(auto i : init){
chk[i] = 1e9+7;
}
init.clear();
chk[0] = 0;
for(auto i : g[cent]){
if(use[i.x]) continue;
//cout << "calc start\n";
ret = min(ret, calc(i.x, cent, i.y, 1));
//cout << "calc end\nupdate start\n";
update(i.x, cent, i.y, 1);
//cout << "update end\n";
}
for(auto i : g[cent]){
if(use[i.x]) continue;
ret = min(ret, solve(i.x));
}
return ret;
}
int best_path(int N, int K, int H[][2], int L[]){
n=N; k=K;
for(int i=0;i<n-1;i++){
g[H[i][0]].push_back({H[i][1],L[i]});
g[H[i][1]].push_back({H[i][0],L[i]});
}
memset(chk, 0x3f, sizeof chk);
int ans = solve(0);
if(ans > 1e9) return -1;
return ans;
}
