#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ed "\n"
#define fi first
#define se second
#define irs insert
#define pb push_back
#define pi pair<int,int>
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x>>i)&1)
#define ON(x, i) ((x) MASK(i))
#define OFF(x, i) ((x) & ~MASK(i))
#define ALL(v) v.begin() , v.end()
#define pii pair<int,pair<int,int>>
#define fl(i,a,b) for(int i=a;i>=b;--i)
#define fis(i,a,b) for(int i=a;i<=b;++i)
const int mod=1e9+7;
const int Mdem=998244353;
const int LOG=19;
const int base=31;
const int maxn=2e5+5;
const int bl = 320;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define gay(a) freopen(a".inp","r",stdin),freopen(a".out","w",stdout)
template <class T>
bool minimize(T &a, const T &b) {
if(a > b) {a = b; return 1;}
return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
if(a < b) {a = b; return 1;}
return 0;
}
template <class T>
void compress(vector <T> &v) {
sort(ALL(v));
v.erase(unique(ALL(v)), (v).end());
}
void add(int &a, int b) { a += b; if (a >= mod) a -= mod; }
void sub(int &a, int b) { a -= b; if (a < 0) a += mod; }
int sz[maxn];
bool is_centroid[maxn];
vector<pi> adj[maxn];
int root = 0, n, k;
int ans = 1e9, dp[maxn];
int mx = 0;
const int N = 1e6 + 1;
struct Segment{
int n;
vector<int> t, del;
Segment(int _n = 0){
n = _n;
t.resize(4 * n + 1);
del.resize(4 * n + 1);
}
void down(int id, int l, int r){
if(del[id]){
t[id * 2] = 1e9; t[id * 2 + 1] = 1e9;
del[id * 2] = del[id]; del[id * 2 + 1] = del[id];
del[id] = 0;
}
}
void update(int id, int l, int r, int pos, int val){
if(pos > r | pos < l) return;
if(l == r){
t[id] = min(t[id], val);
return;
}
down(id, l, r);
int mid = l + r >> 1;
update(id << 1, l, mid, pos, val);
update(id * 2 + 1, mid + 1, r, pos, val);
t[id] = min(t[id << 1], t[id * 2 + 1]);
}
void Clear(int id, int l, int r, int u, int v){
if(v < l || u > r) return;
if(u <= l || v >= r){
t[id] = 1e9;
del[id] = 1;
return;
}
down(id, l, r);
int mid = l + r >> 1;
Clear(id << 1, l, mid, u, v);
Clear(id * 2 + 1, mid + 1, r, u, v);
t[id] = min(t[id << 1], t[id * 2 + 1]);
}
int get(int id, int l, int r, int u, int v){
if(v < l || u > r) return 1e9;
if(l >= u && r <= v) return t[id];
int mid = l + r >> 1;
down(id, l, r);
return min(get(id << 1, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
};
Segment f;
void get(int u, int pa, int h, int val){
if(h > k) return;
int tmp = f.get(1, 1, N, k - h + 1, k - h + 1);
ans = min(ans, tmp + val);
for(pi v : adj[u]) if(v.fi != pa && !is_centroid[v.fi]){
get(v.fi, u, h + v.se, val + 1);
}
}
void update(int u, int pa, int h, int val){
if(h > k) return;
f.update(1, 1, N, h + 1, val);
maximize(mx, h);
for(pi v : adj[u]) if(v.fi != pa && !is_centroid[v.fi]){
update(v.fi, u, h + v.se, val + 1);
}
}
void dfs(int u, int pa){
sz[u] = 1;
for(pi v : adj[u]) if(v.fi != pa && !is_centroid[v.fi]){
dfs(v.fi, u); sz[u] += sz[v.fi];
}
}
int Find_Centroid(int u, int Size, int pa){
for(pi v : adj[u]){
if(v.fi != pa && sz[v.fi] > Size / 2 && !is_centroid[v.fi]){
return Find_Centroid(v.fi, Size, u);
}
}
return u;
}
void Build_Centroid(int u, int pa){
dfs(u, -1);
int centroid = Find_Centroid(u, sz[u], -1);
is_centroid[centroid] = true;
//-----------------------------------------
f.Clear(1, 1, N, 1, N);
f.update(1, 1, N, 1, 0);
mx = 0;
for(pi v : adj[centroid]){
if(!is_centroid[v.fi]){
get(v.fi, centroid, v.se, 1);
update(v.fi, centroid, v.se, 1);
}
}
// f.Clear(1, 1, N, 1, mx + 1);
//-----------------------------------------
for(pi v : adj[centroid]){
if(!is_centroid[v.fi]){
Build_Centroid(v.fi, centroid);
}
}
}
int best_path(int _N, int K, int H[][2], int L[]){
n = _N; k = K;
f = Segment(N);
fis(i, 0, n - 2){
adj[H[i][0] + 1].pb({H[i][1] + 1, L[i]});
adj[H[i][1] + 1].pb({H[i][0] + 1, L[i]});
}
Build_Centroid(1, -1);
if(ans >= 1e9 - 1) return -1;
return ans;
}
