#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
vector<pair<int, int>> adj[N];
int sz[N];
bool vis[N];
int res;
map<int, int> mn;
vector<pair<int, int>> cand;
int dfsSz(int u, int p) {
sz[u] = 1;
for (pair<int, int> v : adj[u]) {
if (v.first != p && !vis[v.first]) {
sz[u] += dfsSz(v.first, u);
}
}
return sz[u];
}
int centroid(int u, int p, int siz) {
for (pair<int, int> v : adj[u]) {
if (v.first != p && !vis[v.first] && sz[v.first] > siz / 2) {
return centroid(v.first, u, siz);
}
}
return u;
}
void dfs(int u, int p, int len, int d) {
cand.emplace_back(len, d);
for (pair<int, int> v : adj[u]) {
if (v.first != p && !vis[v.first]) {
dfs(v.first, u, len + v.second, d + 1);
}
}
}
void build(int u, int k) {
dfsSz(u, -1);
int c = centroid(u, -1, sz[u]);
mn[0] = 0;
for (pair<int, int> v : adj[c]) {
if (!vis[v.first]) {
dfs(v.first, c, v.second, 1);
for (pair<int, int> x : cand) {
int len = x.first;
int d = x.second;
if (mn.find(k - len) != mn.end()) {
res = min(res, mn[k - len] + d);
}
}
for (pair<int, int> x : cand) {
if (mn.find(x.first) == mn.end()) {
mn[x.first] = x.second;
} else {
mn[x.first] = min(mn[x.first], x.second);
}
}
cand.clear();
}
}
mn.clear();
vis[c] = true;
for (pair<int, int> v : adj[c]) {
if (!vis[v.first]) {
build(v.first, k);
}
}
}
int best_path(int n, int k, int h[][2], int l[]) {
for (int i = 0; i < n - 1; i++) {
adj[h[i][0]].emplace_back(h[i][1], l[i]);
adj[h[i][1]].emplace_back(h[i][0], l[i]);
}
res = 1e9;
build(1, k);
return (res == 1e9 ? -1 : res);
}
