#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
const int nu = 3e5+5;
typedef pair<ll, ll> cap;
ll n, k, s[nu], f[nu], ans = 1e9, hh[nu];
bool r[nu];
vector< vector<cap> > g;
multiset<cap> ms;
int dfs(int u, int t)
{
s[u] = 1;
for(cap x : g[u])
{
int v = x.first;
if(r[v] || v == t) continue;
s[u] += dfs(v, u);
}
return s[u];
}
int get_centroid(int u, int t, int sum)
{
for(cap x : g[u])
{
int v = x.first;
if(r[v] || v == t) continue;
if(s[v]*2 > sum) return get_centroid(v, u, sum);
}
return u;
}
void dfs2(int u, int t, int w, int ok)
{
f[u] = f[t]+w; hh[u] = hh[t]+1;
if(f[u] > k) return ;
if(ok == 0)
{
cap o = {k-f[u], 0};
multiset<cap> :: iterator it;
it = lower_bound(ms.begin(), ms.end(), o);
if((*it).first == k-f[u])
ans = min(ans, hh[u]+(*it).second);
}
else ms.insert({f[u], hh[u]});
for(cap x : g[u])
{
int v = x.first;
ll l = x.second;
if(v == t || r[v]) continue;
dfs2(v, u, l, ok);
}
}
void centroid(int u)
{
int cnt = dfs(u, 0);
int c = get_centroid(u, 0, cnt);
r[c] = true;
ms.insert({0, 0});
ms.insert({1e15, 0});
for(cap x : g[c])
{
int v = x.first;
ll l = x.second;
if(r[v]) continue;
dfs2(v, 0, l, 0); dfs2(v, 0, l, 1);
}
while(!ms.empty()) ms.erase(*ms.begin());
for(cap x : g[c])
{
int v = x.first;
if(!r[v]) centroid(v);
}
}
int best_path(int x, int y, int H[][2], int L[])
{
n = x; k = y;
g.resize(n+1);
for(int i = 0; i < n-1; ++i)
{
ll u = H[i][0]; ll v = H[i][1]; ll c = L[i];
u++; v++;
g[u].push_back({v, c});
g[v].push_back({u, c});
}
centroid(1);
if(ans == 1e9) ans = -1;
return ans;
}
