#include <bits/stdc++.h>
#include "race.h"
#define Task "test"
#define ll long long
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair<ll, int> pii;
const int N = int(2e5) + 7;
const int K = int(1e6) + 7;
set<pii>* s[N];
int n, k, u, v, w, res, sz[N], h[N], p[N];
ll d[N];
vector<pii> a[N];
void Build(int u)
{
sz[u] = 1;
for(pii adj: a[u]) {
int v = adj.fi;
if(v == p[u]) continue;
p[v] = u, d[v] = d[u] + adj.se;
h[v] = h[u] + 1, Build(v);
sz[u] += sz[v];
}
}
void Insert(set<pii>* s, ll d, int h)
{
pii found = *(s -> lower_bound(mp(d, -1)));
if(found.se <= h) return;
s -> erase(found);
s -> insert(mp(d, h));
}
void query(int u, int root)
{
if(h[u] - h[root] >= res) return;
int dis = 2 * h[root] + k - h[u];
pii found = *(s[root] -> lower_bound(mp(dis, -1)));
if(found.se + h[u] - 2 * h[root] < res) res = found.se + h[u] - 2 * h[root];
for(pii adj: a[u])
if(adj.fi != p[u]) query(adj.fi, root);
}
void add(int u, int root)
{
if(h[u] - h[root] >= res) return;
Insert(s[root], d[u], h[u]);
for(pii adj: a[u])
if(adj.fi != p[u]) add(adj.fi, root);
}
void DSU(int u)
{
int bigC = -1;
for(pii adj: a[u]) {
if(adj.fi == p[u]) continue;
if(bigC == -1 || sz[adj.fi] > sz[bigC]) bigC = adj.fi;
}
for(pii adj: a[u]) {
if(bigC == adj.fi || adj.fi == p[u]) continue;
DSU(adj.fi);
}
if(bigC != -1) DSU(bigC), s[u] = s[bigC];
else s[u] = new set<pii>();
pii found = *(s[u] -> lower_bound(mp(d[u] + k, -1)));
if(found.fi == d[u] + k) res = min(res, found.se - h[u]);
Insert(s[u], d[u], h[u]);
for(pii adj: a[u]) {
if(bigC == adj.fi || adj.fi == p[u]) continue;
query(adj.fi, u);
add(adj.fi, u);
}
}
int best_path(int N, int K, int adj[][2], int l[])
{
n = N, k = K;
for(int i = 0, lim = n - 1; i < lim; ++i) {
if(l[i] <= K) a[adj[i][0]].pb(adj[i][1], l[i]), a[adj[i][1]].pb(adj[i][0], l[i]);
}
res = n + 1; h[0] = d[0] = p[0] = sz[0] = 0;
Build(0), DSU(0);
if(res == n + 1) return -1;
return res;
}
/*int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if(fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
}
Enter(), Solve();
return 0;
}*/
