#include <bits/stdc++.h>
#include "race.h"
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
vector<ll> dist, depth;
vector<vector<pair<ll, ll>>> adj;
vector<map<ll, ll>> aristas;
void init(ll u, ll p) {
depth[u] = depth[p]+1;
aristas[u][dist[u]] = depth[u];
for (pair<ll, ll> v: adj[u]) {
if (v.fi != p) {
dist[v.fi] = dist[u]+v.se;
init(v.fi, u);
}
}
}
ll k, ans;
void dfs(ll u, ll p) {
for (pair<ll, ll> a: adj[u]) {
ll v = a.fi;
if (v != p) {
dfs(v, u);
if (aristas[v].size() > aristas[u].size()) swap(aristas[v], aristas[u]);
for (auto i: aristas[v]) {
if (aristas[u].find(k+2*dist[u]-i.fi) != aristas[u].end()) {
ans = min(ans, i.se+aristas[u][k+2*dist[u]-i.fi]-2*depth[u]);
}
}
for (auto i: aristas[v]) {
if (aristas[u].find(i.fi) != aristas[u].end()) {
aristas[u][i.fi] = min(aristas[u][i.fi], i.se);
} else {
aristas[u][i.fi] = i.se;
}
}
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
adj = vector<vector<pair<ll, ll>>>(N);
dist = depth = vector<ll>(N);
aristas = vector<map<ll, ll>>(N);
for (int i = 0; i < N-1; ++i) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
dist[0] = 0; depth[0] = -1;
init(0, 0);
k = K;
ans = 1e9;
dfs(0, 0);
if (ans == 1e9) return -1;
return ans;
}
