#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N = 2e5 + 10;
vector<pii> G[N];
int res, mark[N], sz[N], p[N];
void dfs_cen(int u, int r)
{
sz[u] = 1;
for (pii e : G[u])
if (e.fi != r && !mark[e.fi]) p[e.fi] = u, dfs_cen(e.fi, u), sz[u] += sz[e.fi];
}
int h[N];
ll d[N];
void dfs(int u, int r, vi &vt)
{
vt.eb(u);
for (pii e : G[u])
if (e.fi != r && !mark[e.fi])
{
h[e.fi] = h[u] + 1;
d[e.fi] = d[u] + e.se;
dfs(e.fi, u, vt);
}
}
void build_centroid(vi &vt, int K)
{
int len = vt.size();
dfs_cen(vt[0], 0);
int root = vt[0];
for (int x : vt)
{
int mx = len - sz[x];
for (pii e : G[x])
if (!mark[e.fi] && e.fi != p[x]) mx = max(mx, sz[e.fi]);
if (mx <= len / 2) root = x;
}
mark[root] = 1;
vector<vi> vt_sub;
map<ll,int> best;
best[0] = 0;
h[root] = 0;
for (pii e : G[root])
if (!mark[e.fi])
{
h[e.fi] = 1;
d[e.fi] = e.se;
vi s;
dfs(e.fi, root, s);
for (int x : s)
if (d[x] <= K && best.count(K - d[x])) res = min(res, h[x] + best[K - d[x]]);
for (int x : s)
if (!best.count(d[x])) best[d[x]] = h[x];
else best[d[x]] = min(best[d[x]], h[x]);
vt_sub.eb(s);
}
for (vi s : vt_sub) build_centroid(s, K);
}
int best_path(int n, int K, int H[][2], int L[])
{
for (int i = 1; i <= n; ++i) G[i].clear(), mark[i] = 0;
for (int i = 0; i < n - 1; ++i)
{
int u = H[i][0] + 1;
int v = H[i][1] + 1;
int w = L[i];
G[u].eb(v,w);
G[v].eb(u,w);
}
res = 1e9;
vi vt;
for (int i = 1; i <= n; ++i) vt.eb(i);
build_centroid(vt, K);
if (res == 1e9) res = -1;
return res;
}
