#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#define pb push_back
#define ins insert
#define fi first
#define se second
#define mod (ll)(1e9 + 7)
#define mxn (ll)(2e5 + 5)
#define inf (ll)(0x3F3F3F3F)
int n, k;
vector<pii> adj[mxn];
int sz[mxn];
int used[mxn];
inline void getsize(int a, int p)
{
sz[a] = 1;
for (pii v : adj[a])
{
if (used[v.fi] || v.fi == p) continue;
getsize(v.fi, a);
sz[a] += sz[v.fi];
}
}
inline int findcent(int a, int p, int &curn)
{
for (pii v : adj[a])
{
if (used[v.fi] || v.fi == p) continue;
if (sz[v.fi] > curn/2) return findcent(v.fi, a, curn);
}
return a;
}
vector<pii> arr;
pii mp[(int)(1e6 + 5)];
int res = inf;
int curc;
inline void init(int a, int p, int w, int w1)
{
if (k - w >= 0 && mp[k - w].se == curc)
{
res = min(res, mp[k - w].fi + w1);
}
arr.pb({w, w1});
for (pii v : adj[a])
{
if (used[v.fi] || v.fi == p) continue;
init(v.fi, a, w + v.se, w1 + 1);
}
}
inline void maincent(int a)
{
getsize(a, a);
int c = findcent(a, a, sz[a]);
curc = c;
mp[0] = {0, c};
for (pii v : adj[c])
{
if (used[v.fi]) continue;
arr.clear();
init(v.fi, c, v.se, 1);
for (pii x : arr)
{
if (x.fi > k) continue;
if (mp[x.fi].se != curc) mp[x.fi] = {x.se, curc};
else mp[x.fi].fi = min(mp[x.fi].fi, (int)x.se);
}
}
used[c] = 1;
for (pii v : adj[c])
{
if (used[v.fi]) continue;
maincent(v.fi);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
for (int i = 0; i < (int)(1e6 + 5); i++) mp[i] = {0, -1};
n = N;
k = K;
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]});
}
maincent(0);
return (res == inf ? -1 : res);
}
