#include "race.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
constexpr int MAX = 2e+5 + 1, INF = 2e+9, MOD = 1e+9 + 7, K = 28;
int k;
vector <pair<int, int>> g[MAX+2];
vector <int> st(MAX+2), is(MAX+2);
vector <pair<int, int>> dis;
map <int, int> mx;
int res=INF;
void dfs(int u, int c=-1) {
st[u] = 1;
for (auto &i : g[u]) {
if (i.ff == c || is[i.ff]) continue;
dfs(i.ff, u);
st[u] += st[i.ff];
}
}
int get(int u, int s, int c=-1) {
for (auto &i : g[u]) {
if (i.ff == c || is[i.ff]) continue;
if (st[i.ff] * 2 > s) return get(i.ff, s, u);
}
return u;
}
void dist(int u, int lv=0, int w=0, int c=-1) {
if (w <= k) dis.pb({w, lv});
else return;
for (auto &i : g[u]) {
if (i.ff == c || is[i.ff]) continue;
dist(i.ff, lv+1, w+i.ss, u);
}
}
void build(int u) {
dfs(u);
int c = get(u, st[u]);
is[c] = 1;
mx.clear();
mx[0] = 0;
for (auto &i : g[c]) {
if (is[i.ff]) continue;
dis.clear();
dist(i.ff, 1, i.ss, c);
for (auto &j : dis) {
if (mx[k-j.ff] == 0 && k != j.ff) continue;
res = min(res, mx[k-j.ff] + j.ss);
}
for (auto &j : dis) {
if (mx[j.ff] == 0) {
mx[j.ff] = j.ss;
}
mx[j.ff] = min(mx[j.ff], j.ss);
}
}
for (auto &i : g[c]) {
if (is[i.ff]) continue;
build(i.ff);
}
}
int best_path(int n, int K, int H[][2], int L[]) {
k = K;
for (int i = 0; i < n-1; i++) {
g[H[i][0]+1].pb({H[i][1]+1, L[i]});
g[H[i][1]+1].pb({H[i][0]+1, L[i]});
}
build(1);
return (res == INF ? -1 : res);
}
