#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
const int MOD = 1e9+7; // 998244353;
vctr<pii> adj[200005];
map<ll,int> mp[200005];
pli d[200005];
int ans = 2e9;
int k;
void dfs(int node, int fa) {
for (auto [it,w] : adj[node]) {
if (it == fa)continue;
dfs(it,node);
d[it].f += w;
++d[it].s;
if (mp[it].size() > mp[node].size())swap(mp[it],mp[node]), swap(d[it],d[node]);
for (auto it2 : mp[it]) {
ll x = it2.f+d[it].f;
int y = it2.f+d[it].s;
if (mp[node].find(k-x-d[node].f) != mp[node].end()) {
amin(ans,mp[node][k-x-d[node].f]+d[node].s+y);
}
}
for (auto it2 : mp[it]) {
ll x = it2.f+d[it].f;
int y = it2.f+d[it].s;
if (mp[node].find(x-d[node].f) != mp[node].end()) {
mp[node][x-d[node].f] = y-d[node].s;
} else {
amin(mp[node][x-d[node].f],y-d[node].s);
}
}
}
if (mp[node].find(k-d[node].f) != mp[node].end()) {
amin(ans,mp[node][k-d[node].f]+d[node].s);
}
mp[node][-d[node].f] = -d[node].s;
// dbg(node-1);
// for (auto [x,y] : mp[node]) {
// cout << x+d[node].f << ' ' << y+d[node].s << '\n';
// }
return;
}
int best_path(int N, int K, int H[][2], int L[])
{
int n = N;
k = K;
ans = 2e9;
for (int i = 1; i <= n-1; ++i) {
int u = H[i-1][0];
int v = H[i-1][1];
int w = L[i-1];
++u;
++v;
adj[u].eb(v,w);
adj[v].eb(u,w);
}
dfs(1,0);
if (ans == (int)2e9)ans = -1;
return ans;
}
