#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int N, K;
vector<pair<int,int>> g[200005];
bool used[200005];
int sz[200005];
int ans = INF;
unordered_map<int,int> best;
/* Tính size subtree */
void dfs_sz(int u, int p) {
sz[u] = 1;
for (auto [v, w] : g[u]) {
if (v == p || used[v]) continue;
dfs_sz(v, u);
sz[u] += sz[v];
}
}
/* Tìm centroid */
int dfs_centroid(int u, int p, int n) {
for (auto [v, w] : g[u]) {
if (v == p || used[v]) continue;
if (sz[v] > n / 2)
return dfs_centroid(v, u, n);
}
return u;
}
/* Thu thập (distance, edges) */
void dfs_collect(int u, int p, int dist, int edges, vector<pair<int,int>>& vec) {
if (dist > K) return;
vec.push_back({dist, edges});
for (auto [v, w] : g[u]) {
if (v == p || used[v]) continue;
dfs_collect(v, u, dist + w, edges + 1, vec);
}
}
/* Xử lý tại centroid */
void solve(int c) {
best.clear();
best[0] = 0;
for (auto [v, w] : g[c]) {
if (used[v]) continue;
vector<pair<int,int>> vec;
dfs_collect(v, c, w, 1, vec);
for (auto [d, e] : vec) {
if (best.count(K - d))
ans = min(ans, e + best[K - d]);
}
for (auto [d, e] : vec) {
if (!best.count(d))
best[d] = e;
else
best[d] = min(best[d], e);
}
}
}
/* Centroid decomposition */
void decompose(int u) {
dfs_sz(u, -1);
int c = dfs_centroid(u, -1, sz[u]);
used[c] = true;
solve(c);
for (auto [v, w] : g[c]) {
if (!used[v])
decompose(v);
}
}
int best_path(int n, int k, vector<vector<int>> H, vector<int> L) {
N = n;
K = k;
for (int i = 0; i < N; i++) g[i].clear(), used[i] = false;
for (int i = 0; i < N - 1; i++) {
int u = H[i][0];
int v = H[i][1];
int w = L[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
ans = INF;
decompose(0);
return (ans == INF ? -1 : ans);
}
