#include <bits/stdc++.h>
using namespace std;
static const int INF = 1e9;
static int N_, K_;
static vector<vector<pair<int,int>>> g;
static vector<int> sz;
static vector<char> dead;
static int answer;
static void dfs_size(int u, int p){
sz[u] = 1;
for (auto [v, w] : g[u]) if (v != p && !dead[v]){
dfs_size(v, u);
sz[u] += sz[v];
}
}
static int find_centroid(int u, int p, int tot){
for (auto [v, w] : g[u]) if (v != p && !dead[v]){
if (sz[v] * 2 > tot) return find_centroid(v, u, tot);
}
return u;
}
static void collect(int u, int p, int dist, int edges, vector<pair<int,int>>& vec){
if (dist > K_) return;
vec.emplace_back(dist, edges);
for (auto [v, w] : g[u]) if (v != p && !dead[v]){
collect(v, u, dist + w, edges + 1, vec);
}
}
static void solve_centroid(int c){
vector<int> best(K_ + 1, INF);
best[0] = 0;
for (auto [v, w] : g[c]) if (!dead[v]){
vector<pair<int,int>> buf;
collect(v, c, w, 1, buf);
for (auto [d, e] : buf){
if (d <= K_){
int need = K_ - d;
if (best[need] != INF) answer = min(answer, e + best[need]);
}
}
for (auto [d, e] : buf){
if (d <= K_) best[d] = min(best[d], e);
}
}
}
static void decompose(int entry){
dfs_size(entry, -1);
int c = find_centroid(entry, -1, sz[entry]);
dead[c] = 1;
solve_centroid(c);
for (auto [v, w] : g[c]) if (!dead[v]){
decompose(v);
}
}
int best_path(int N, int K, int H[][2], int L[]){
N_ = N; K_ = K;
if (K_ == 0) return 0;
g.assign(N_, {});
sz.assign(N_, 0);
dead.assign(N_, 0);
answer = INF;
for (int i = 0; i < N_ - 1; ++i){
int u = H[i][0], v = H[i][1], w = L[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
decompose(0);
return (answer == INF ? -1 : answer);
}
