#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2e5 + 10;
const int MAXK = 1e6 + 10;
int used[MAXN], sub[MAXN];
ll dist[MAXN];
int freq[MAXN];
vector<pair<int, int>> adj[MAXN];
int ans, k;
int get_size(int v, int p){
sub[v] = 1;
for(auto [u, w] : adj[v]){
if(u == p || used[u]) continue;
sub[v] += get_size(u, v);
}
return sub[v];
}
int get_centroid(int v, int p, int sz){
for(auto [u, w] : adj[v]){
if(u == p || used[u]) continue;
if(sub[u] > sz / 2) return get_centroid(u, v, sz);
}
return v;
}
void get_dist(int v, int p){
if(dist[v] <= k) freq[dist[v]] = 1e9;
for(auto [u, w] : adj[v]){
if(u == p || used[u]) continue;
dist[u] = dist[v] + w;
get_dist(u, v);
}
}
void upd_freq(int v, int p, int d, int x){
if(dist[v] > k) return;
if(x == 0){
ans = min(ans, d + freq[k - dist[v]]);
} else freq[dist[v]] = min(freq[dist[v]], d);
for(auto [u, w] : adj[v]){
if(u == p || used[u]) continue;
upd_freq(u, v, d + 1, x);
}
}
void build(int v, int p){
int c = get_centroid(v, p, get_size(v, p));
used[c] = 1;
dist[c] = 0;
get_dist(c, c);
freq[0] = 0;
for(auto [u, w] : adj[c]){
if(used[u]) continue;
upd_freq(u, c, 1, 0);
upd_freq(u, c, 1, 1);
}
get_dist(c, c);
for(auto [u, w] : adj[c]){
if(used[u]) continue;
build(u, c);
}
}
int best_path(int n, int k_, int h[][2], int l[]){
k = k_;
for(int i=0; i<n-1; i++){
adj[h[i][0] + 1].push_back({h[i][1] + 1, l[i]});
adj[h[i][1] + 1].push_back({h[i][0] + 1, l[i]});
}
ans = 1e9;
build(1, 1);
return (ans == 1e9 ? -1 : ans);
}
