#include <bits/stdc++.h>
#include "race.h"
//#include "grader.cpp"
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int Nmax = 2e5 + 5;
vector <pair <int, int>> adj[Nmax];
map <int, int> s[Nmax];
int k, ans = 1e9;
void dfs(int u, int p) {
s[u][0] = 0;
for (pair <int, int> e : adj[u]){
int v = e.fi;
int w = e.se;
if (v == p)
continue;
dfs(v, u);
if (s[u].size() < s[v].size())
swap(s[u], s[v]);
for (pair <int, int> pir : s[v])
if (s[u].count(k - pir.fi - w))
ans = min(ans, s[u][k - pir.fi - w] + pir.se + 1);
for (pair <int, int> pir : s[v]) if (pir.fi + w <= k) {
if (!s[u].count(pir.fi + w))
s[u][pir.fi + w] = pir.se + 1;
else
s[u][pir.fi + w] = min(s[u][pir.fi + w], pir.se + 1);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for (int i = 0; i < N - 1; i++) {
int u = H[i][0];
int v = H[i][1];
adj[u].push_back(mp(v, L[i]));
adj[v].push_back(mp(u, L[i]));
}
dfs(0, -1);
if (ans == 1e9)
ans = -1;
cerr << ans << "\n";
return ans;
}
