#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int) (a).size()
#define ll long long
#define ld long double
struct P{
ll x, y;
};
void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
const ll MX = 2e5+5;
vector<pair<ll, ll>> g [MX];
vector<ll> tour;
ll depth[MX], s[MX], st[MX], ed[MX];
ll dist[MX];
void calc(ll x, ll y, ll dp, ll ds){
s[x] = 1;
depth[x] = dp;
st[x] = sz(tour);
tour.push_back(x);
dist[x] = ds;
for (auto [z, w]: g[x]){
if (z == y) continue;
calc(z, x, dp+1, ds+w);
s[x] += s[z];
}
ed[x] = sz(tour);
}
ll ans=MX+1;
ll delta = 0;
ll deltb = 0;
map<ll, ll> path;
set<ll> exists;
set<pair<ll, ll>> paths;
void dfs(ll x, ll y, ll k, bool keep){
ll big=-1, bsize=-1, bdelta=0;
for (auto [z, w]: g[x]){
if (z == y) continue;
if (s[z] > bsize) big = z, bsize = s[z], bdelta = w;
}
for (auto [z, w]: g[x]){
if (z == y || z == big) continue;
dfs(z, x, k, 0);
}
if (big != -1) dfs(big, x, k, 1), delta += bdelta, deltb++;
// apply your delta to paths
for (auto [z, w]: g[x]){
if (z == y || z == big) continue;
for (ll i=st[z]; i<ed[z]; i++){
ll ds = dist[tour[i]] - dist[x];
ll d = depth[tour[i]] - depth[x];
if (!exists.count(k-ds-delta)) continue;
ans = min(ans, d + path[k-ds-delta] + deltb);
}
for (ll i=st[z]; i<ed[z]; i++){
ll ds = dist[tour[i]] - dist[x];
ll d = depth[tour[i]] - depth[x];
if (exists.count(k-ds-delta)) path[ds-delta] = min(path[ds-delta], d - deltb);
else{
exists.insert(ds-delta);
path[ds-delta] = d - deltb;
}
}
}
if (exists.count(k-delta)){
ans = min(path[k-delta] + deltb, ans);
}
exists.insert(-delta);
path[-delta] = -deltb;
if (keep) return;
exists.clear();
path.clear();
delta = 0;
deltb = 0;
}
int best_path(int n, int k, int edges[][2], int weights[]){
for (int i=0; i<n-1; i++){
g[edges[i][0]].push_back({edges[i][1], weights[i]});
g[edges[i][1]].push_back({edges[i][0], weights[i]});
}
calc(0, 0, 0, 0);
dfs(0, 0, k, 1);
if (ans == MX+1) return -1;
else return ans;
}
