#include "race.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
const int sz = 2e5 + 5;
int n, m, k, ans = sz, w[sz], len[sz], used[sz], d[sz];
vector<array<int, 2>> g[sz];
vector<int> cur;
map<int, int> mp;
void dfs(int v, int p)
{
w[v] = 1;
for(auto i : g[v])
{
if(i[0] == p) continue;
dfs(i[0], v);
w[v] += w[i[0]];
}
}
int fnd(int v, int p = -1)
{
for(auto i : g[v])
{
if(i[0] == p || used[i[0]]) continue;
if(w[i[0]] > w[v] / 2)
{
w[v] -= w[i[0]];
w[i[0]] += w[v];
return fnd(i[0], v);
}
}
return v;
}
void dist(int v, int p, int cst)
{
if(d[p] + cst > k) return;
len[v] = len[p] + 1;
d[v] = d[p] + cst;
cur.push_back(v);
for(auto i : g[v])
{
if(i[0] == p || used[i[0]]) continue;
dist(i[0], v, i[1]);
}
}
void build(int v)
{
int c = fnd(v);
used[c] = 1;
d[c] = 0;
len[c] = 0;
mp[0] = 0;
for(auto x : g[c])
{
if(used[x[0]]) continue;
dist(x[0], c, x[1]);
for(int j : cur)
{
if(mp.find(k - d[j]) != mp.end())
ans = min(ans, mp[k - d[j]] + len[j]);
}
for(int j : cur)
{
if(mp.find(d[j]) == mp.end()) mp[d[j]] = len[j];
else mp[d[j]] = min(mp[d[j]], len[j]);
}
}
cur.clear();
mp.clear();
for(auto x : g[c])
{
if(!used[x[0]])
build(x[0]);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K;
for(int i = 1; i <= n; i++)
{
g[i].clear();
w[i] = 0;
len[i] = 0;
d[i] = 0;
used[i] = 0;
}
mp.clear();
cur.clear();
ans = sz;
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]});
}
dfs(1, 1);
build(1);
if(ans >= sz) ans = -1;
return ans;
}
