#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 <long long, int> s[Nmax];
long long val[Nmax];
int cnt[Nmax];
int k, ans = 1e9;
void dfs(int u, int p) {
int vmax = u;
for (pair <int, int> e : adj[u]){
int v = e.fi;
int w = e.se;
if (v == p)
continue;
dfs(v, u);
if (s[v].size() > s[vmax].size()) {
vmax = v;
cnt[u] = cnt[vmax] + 1;
val[u] = val[vmax] + w;
}
}
swap(s[u], s[vmax]);
if (!s[u].count(-val[u]))
s[u][-val[u]] = -cnt[u];
else
s[u][-val[u]] = min(s[u][-val[u]], -cnt[u]);
if (vmax == u)
return;
for (pair <int, int> e : adj[u]) {
int v = e.fi;
int w = e.se;
if (v == vmax)
continue;
for (pair <long long, int> pir : s[v]) {
long long res = k - (pir.fi + val[v] + w) - val[u];
if (s[u].count(res))
ans = min(ans, (s[u][res] + cnt[u]) + (pir.se + cnt[v]) + 1);
}
for (pair <long long, int> pir : s[v]) {
long long res = (pir.fi + val[v] + w) - val[u];
int rescnt = (pir.se + cnt[v] + 1) - cnt[u];
if (!s[u].count(res))
s[u][res] = rescnt;
else
s[u][res] = min(s[u][res], rescnt);
}
}
// cout << "Path " << u << ": \n";
// for (pair <long long, int> pir : s[u])
// cout << pir.fi + val[u] << " " << pir.se + cnt[u] << "\n";
}
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;
return ans;
}
