#include "race.h"
#include <bits/stdc++.h>
#define MN 200071
#define MK 20
using namespace std;
using ll = long long;
vector<pair<int, int> > L[MN];
namespace LCA {
static inline int log2(const int &v) {
return 31 - __builtin_clz(v);
}
int In[MN], Out[MN], tmr;
ll Niv[MN], RMQ[MK][MN * 2];
void dfi(int u, int p, int niv) {
In[u] = Out[u] = ++tmr;
RMQ[0][In[u]] = Niv[u] = niv;
for(auto [it, w] : L[u]) if(it != p) {
dfi(it, u, niv + w);
RMQ[0][Out[u] = ++tmr] = Niv[u];
}
}
void init(int n) {
for(int k = 1; k < MK; ++k)
for(int i = 1; i <= n; ++i)
RMQ[k][i] = min(RMQ[k-1][i], RMQ[k-1][i + (1 << (k-1))]);
}
int query(int st, int dr) {
int l = log2(dr - st + 1);
return min(RMQ[l][st], RMQ[l][dr - (1 << l) + 1]);
}
int dist(int u, int v) {
return Niv[u] + Niv[v] - 2 * query(min(In[u], In[v]), max(Out[u], Out[v]));
}
}
bool Used[MN];
int Sz[MN];
void dfi(int u, int p) {
Sz[u] = 1;
for(auto &[it, w] : L[u])
if(it != p && !Used[it]) dfi(it, u), Sz[u] += Sz[it];
}
int centr(int u, int p, const int &sz) {
for(auto [it, w] : L[u])
if(it != p && !Used[it] && Sz[it] * 2 > sz) return centr(it, u, sz);
return u;
}
void dfc(int u, int p, vector<tuple<int, ll, int> > &comp, ll d, int niv = 1) {
comp.push_back({u, d, niv});
for(auto [it, w] : L[u])
if(it != p && !Used[it])
dfc(it, u, comp, d + w, niv + 1);
}
void desc(int u, int par_comp, int k, int &rez) {
dfi(u, 0);
int c = centr(u, 0, Sz[u]);
map<ll, int> Posib;
Used[c] = 1;
Posib[0] = 0;
for(auto [it, w] : L[c]) {
if(Used[it]) continue;
vector<tuple<int, ll, int> > comp;
dfc(it, c, comp, w);
for(auto &[u, dist, niv] : comp)
if(Posib.count(k - dist)) rez = min(rez, niv + Posib[k - dist]);
for(auto &[u, dist, niv] : comp)
if(!Posib.count(dist)) Posib[dist] = niv;
else Posib[dist] = min(Posib[dist], niv);
}
for(auto &[it, w] : L[c])
if(!Used[it])
desc(it, c, k, rez);
}
int best_path(int N, int K, int H[][2], int W[]) {
for(int i = 0; i < N - 1; ++i) {
L[H[i][0] + 1].push_back({H[i][1] + 1, W[i]});
L[H[i][1] + 1].push_back({H[i][0] + 1, W[i]});
}
int rez = numeric_limits<int>::max() / 4;
desc(1, 0, K, rez);
if(rez == numeric_limits<int>::max() / 4) rez = -1;
return rez;
}
