#include <bits/stdc++.h>
using namespace std;
#include "race.h"
#define int long long
const int MX = 2e5 + 10;
int n, k, ans = 1e9, timer = 0, tin[MX], tout[MX], rev[MX], d[MX], ed[MX], siz[MX], bigc[MX];
vector<pair<int,int>> adj[MX];
map<int, int> mnedge;
void dfs2(int v,int p, bool keep){// keep
for(auto [e, w] : adj[v]){
if(p != e && bigc[v] != e)dfs2(e, v, false);
}
if(bigc[v] != -1)dfs2(bigc[v], v, true);
mnedge[d[v]] = ed[v];
if(mnedge.find(d[v] + k) != mnedge.end())
ans = min(ans, mnedge[d[v] + k] - ed[v]);
for(auto [e, w] : adj[v]){
if(e == p || e == bigc[v])continue;
for(int st = tin[e];st<=tout[e];st++){
int node = rev[st];
int c = k + 2*d[v] - d[node];
if(mnedge.find(c) != mnedge.end())ans = min(ans, mnedge[c] + ed[node] - 2*ed[v]);
}
for(int st = tin[e];st<=tout[e];st++){
if(mnedge[d[rev[st]]] == 0)
mnedge[d[rev[st]]] = ed[rev[st]];
else
mnedge[d[rev[st]]] = min(mnedge[d[rev[st]]], ed[rev[st]]);
}
}
if(!keep){
mnedge.clear();
}
}
void dfs1(int v,int p){
int mx = -1;
rev[++timer] = v;
tin[v] = timer;
bigc[v] = -1;
siz[v] = 1;
for(auto [e, w] : adj[v]){
if(e == p)continue;
d[e] = d[v] + w;
ed[e] = ed[v] + 1;
dfs1(e, v);
if(siz[e] > mx){
bigc[v] = e;
mx = siz[e];
}
siz[v] += siz[e];
}
tout[v] = timer;
}
#undef int
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
for(int i = 0;i + 1<n;i++){
int a = H[i][0], b = H[i][1], c = L[i];
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
dfs1(0, -1);
dfs2(0, -1, true);
if(ans > 1e8)
return -1;
return ans;
}
// signed main() {
// iostream::sync_with_stdio(0);cin.tie(0);
// }
