#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
const int N = 2e5 + 5;
int k;
vpii adj[N];
int h[N];
ll d[N];
int sz[N];
void dfs_sz(int u, int p = -1){
sz[u] = 1;
for (auto [v, w]: adj[u]){
if (v == p){
continue;
}
h[v] = h[u] + 1;
d[v] = d[u] + w;
dfs_sz(v, u);
sz[u] += sz[v];
}
}
int ans = INT_MAX;
gp_hash_table <ll, int> mpp[N];
void dfs_mergeset(int u, int p = -1){
int heavy = -1;
for (auto [v, w]: adj[u]){
if (v == p){
continue;
}
dfs_mergeset(v, u);
if (heavy == -1 or sz[heavy] < sz[v]){
heavy = v;
}
}
if (heavy != -1){
mpp[u].swap(mpp[heavy]);
}
for (auto [v, w]: adj[u]){
if (v == p or v == heavy){
continue;
}
for (auto [dpath, hpath]: mpp[v]){
auto itr = mpp[u].find(k + 2 * d[u] - dpath);
if (itr != mpp[u].end()){
ans = min(ans, hpath + itr->se - 2 * h[u]);
}
}
for (auto [dpath, hpath]: mpp[v]){
auto itr = mpp[u].find(dpath);
if (itr != mpp[u].end()){
itr->se = min(itr->se, hpath);
}
else{
mpp[u][dpath] = hpath;
}
}
}
{
auto itr = mpp[u].find(k + d[u]);
if (itr != mpp[u].end()){
ans = min(ans, itr->se - h[u]);
}
mpp[u][d[u]] = h[u];
}
}
int best_path(int n, int _k, int edge[][2], int weight[]){
k = _k;
For(i, 0, n - 1){
auto [u, v, w] = tuple{edge[i][0], edge[i][1], weight[i]};
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
dfs_sz(0);
dfs_mergeset(0);
if (ans == INT_MAX){
ans = -1;
}
return ans;
}
/*
==================================================+
INPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
