#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
class centroid_decomposition {
private:
int n, r;
vector< vector<int> > g, cd;
vector<int> sz;
vector<bool> used;
void build() {
n = (int) g.size();
cd.resize(n);
sz.resize(n);
used.assign(n, false);
dfs(0, -1);
}
void get_sizes(int u, int p) {
sz[u] = 1;
for (auto& v : g[u]) {
if (!used[v] && v != p) {
get_sizes(v, u);
sz[u] += sz[v];
}
}
}
int find_centroid(int u, int p, int n) {
for (auto& v : g[u]) if (!used[v] && v != p && sz[v] > n / 2) return find_centroid(v, u, n);
return u;
}
void dfs(int u, int p) {
get_sizes(u, p);
int n = sz[u];
int centroid = find_centroid(u, p, n);
if (p != -1) cd[p].push_back(centroid);
else r = centroid;
used[centroid] = true;
for (auto& v : g[centroid]) {
if (!used[v] && v != p) {
dfs(v, centroid);
}
}
}
public:
centroid_decomposition() {}
centroid_decomposition(const vector< vector<int> > &_g) : g(_g) {
build();
}
centroid_decomposition(const vector< vector< pair<int, int> > > &_g) {
for (auto& u : _g) {
g.push_back({});
for (auto& p : u) g.back().push_back(p.first);
}
build();
}
const vector<int> &operator[](const int &u) {
return cd[u];
}
int root() {
return r;
}
};
int n, k, max_log, dfs_cnt = 0;
vector< vector< pair<int, int> > > g;
vector< vector<int> > up;
vector<int> dfs_in, dfs_out, cnt;
vector<long long> d;
void dfs(int u, int p) {
up[u][0] = p;
dfs_in[u] = dfs_cnt++;
for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for (auto& v : g[u]) {
if (v.first != p) {
cnt[v.first] = cnt[u] + 1;
d[v.first] = d[u] + v.second;
dfs(v.first, u);
}
}
dfs_out[u] = dfs_cnt++;
}
bool is_anc(int u, int v) {
return dfs_in[u] <= dfs_in[v] && dfs_out[v] <= dfs_out[u];
}
int lca(int u, int v) {
if (is_anc(u, v)) return u;
if (is_anc(v, u)) return v;
for (int i = max_log; i >= 0; i--) if (!is_anc(up[u][i], v)) u = up[u][i];
return up[u][0];
}
centroid_decomposition cd;
vector<int> order, st, en;
int dfs(int u) {
int ans = INF;
st[u] = en[u] = (int) order.size();
order.push_back(u);
map<long long, int> mp; mp[0] = 0;
for (auto &v : cd[u]) {
ans = min(ans, dfs(v));
for (int i = st[v]; i <= en[v]; i++) {
long long dist = d[u] + d[order[i]] - 2 * d[lca(u, order[i])];
if (mp.count(k - dist)) ans = min(ans, mp[k - dist] + cnt[u] + cnt[order[i]] - 2 * cnt[lca(u, order[i])]);
}
for (int i = st[v]; i <= en[v]; i++) {
long long dist = d[u] + d[order[i]] - 2 * d[lca(u, order[i])];
int edges = cnt[u] + cnt[order[i]] - 2 * cnt[lca(u, order[i])];
if (mp.count(dist)) mp[dist] = min(mp[dist], edges);
else mp[dist] = edges;
}
en[u] = en[v];
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
g.resize(n);
for (int i = 0; i < n - 1; i++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
max_log = ceil(log2(n));
up.assign(n, vector<int>(max_log + 1));
dfs_in.resize(n);
dfs_out.resize(n);
d.resize(n); d[0] = 0;
cnt.resize(n); cnt[0] = 0;
dfs(0, 0);
cd = centroid_decomposition(g);
st.resize(n);
en.resize(n);
int ans = dfs(cd.root());
if (ans == INF) return -1;
return ans;
}
