#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
const ll M = 1e6 + 5;
int k, sz[M];
vector<pii> adj[M];
vector<pair<int, ll>> pool;
vector<ll> vals;
bool vis[M];
int dp[M];
ll ans;
int dfsSz(int u, int par) {
sz[u] = 1;
for (auto v: adj[u]) {
if (v.fi == par || vis[v.fi])continue;
dfsSz(v.fi, u);
sz[u] += sz[v.fi];
}
return sz[u];
}
int dfsCenter(int u, int par, int size) {
for (auto v: adj[u]) {
if (v.fi == par || vis[v.fi])continue;
if (sz[v.fi] * 2 > size)
return dfsCenter(v.fi, u, size);
}
return u;
}
void collect(int u, int par, ll sum, int dep) {
pool.emplace_back(sum, dep);
vals.push_back(sum);
for (auto v: adj[u]) {
if (v.fi == par || vis[v.fi])continue;
collect(v.fi, u, sum + v.se, dep + 1);
}
}
void build(int u, int par) {
int size = dfsSz(u, par);
int centroid = dfsCenter(u, par, size);
if (par == -1)
par = centroid;
vis[centroid] = true;
for (auto v: adj[centroid]) {
if (v.fi == par || vis[v.fi])continue;
pool.clear();
collect(v.first, centroid, v.se, 1);
for (auto &i: pool) {
if (i.first > k)continue;
ans = min(ans, dp[k - i.first] + i.second);
}
for (auto &i: pool) {
if (i.first > k)continue;
dp[i.first] = min(1ll * dp[i.first], i.second);
}
}
for (long long val: vals) {
if (val > k)continue;
dp[val] = 1e9;
}
vals.clear();
for (auto v: adj[centroid]) {
if (v.fi == par || vis[v.fi])continue;
build(v.fi, centroid);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 1; i < M; ++i) {
dp[i] = 1e9;
}
ans = 1e9;
for (int i = 0; i < N - 1; ++i) {
int u = H[i][0] - 1;
int v = H[i][1] - 1;
adj[u].emplace_back(v,L[i]);
adj[v].emplace_back(u,L[i]);
}
k = K;
build(0,0);
if(ans == 1e9){
ans = -1;
}
return ans;
}
