#include "race.h"
#include <vector>
using namespace std;
#define f first
#define s second
#define pii pair<int, int>
const int MAX_N = 200001;
vector<pii> edges[MAX_N], lengths;
vector<int> cur;
int k, num[MAX_N], best[1000001], ans = 1e9;
bool removed[MAX_N];
int dfs(int v, int p) {
num[v] = 1;
for (pii u : edges[v]) {
if (u.f != p && !removed[u.f]) num[v] += dfs(u.f, v);
}
return num[v];
}
int centroid(int v, int p, int n) {
for (pii u : edges[v]) {
if (u.f != p && !removed[u.f] && num[u.f]>n/2) return centroid(u.f, v, n);
}
return v;
}
void getlengths(int v, int p, int c, int d) {
if (c > k) return;
lengths.emplace_back(c, d);
for (pii u : edges[v]) {
if (u.f != p && !removed[u.f]) getlengths(u.f, v, c+u.s, d+1);
}
}
void solve(int v) {
removed[v] = true;
for (pii u : edges[v]) {
if (!removed[u.f]) {
lengths.clear();
getlengths(u.f, v, u.s, 1);
for (pii length : lengths) {
if (length.f == k) ans = min(ans, length.s);
ans = min(ans, length.s+best[k-length.f]);
cur.push_back(length.f);
}
for (pii length : lengths) best[length.f] = min(best[length.f], length.s);
}
}
for (int i : cur) best[i] = 1e9;
cur.clear();
for (pii u : edges[v]) {
if (!removed[u.f]) solve(centroid(u.f, u.f, dfs(u.f, u.f)));
}
}
int best_path(int n, int K, int H[][2], int L[]) {
k = K;
for (int i=0; i<n-1; i++) {
edges[H[i][0]].emplace_back(H[i][1], L[i]);
edges[H[i][1]].emplace_back(H[i][0], L[i]);
}
for (int i=0; i<1000001; i++) best[i] = 1e9;
dfs(0, 0);
solve(centroid(0, 0, n));
return ans==1e9 ? -1 : ans;
}
