#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
const int MX = 2e5 + 10;
const int INF = 1e9;
int _K, off[MX], ans = INF; ll dep[MX];
map<ll, int>* dp[MX];
vector<pii> adj[MX];
void ae(int u, int v, int w){
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
void chmin(int& a, int b){
if(b < a) a = b;
}
void add(int u, int v, int cdep){ // add dp of v to dp of u
if(dp[u] -> size() < dp[v] -> size()) swap(dp[u], dp[v]), swap(off[u], off[v]);
for(pii x : (*dp[v])){
int len = _K + 2 * cdep - x.fi;
if(dp[u] -> count(len)) chmin(ans, x.se + off[v] + (*dp[u])[len] + off[u]);
}
for(pii x : (*dp[v])){
if(dp[u] -> count(x.fi)) chmin((*dp[u])[x.fi], x.se + off[v] - off[u]);
else (*dp[u])[x.fi] = x.se + off[v] - off[u];
}
}
void dfs(int u, int v){
dp[u] = new map<ll, int>();
(*dp[u])[dep[u]] = 0;
off[u] = 0;
for(pii nxt : adj[u]){
if(nxt.fi == v) continue;
dep[nxt.fi] = dep[u] + nxt.se;
dfs(nxt.fi, u);
off[nxt.fi]++;
add(u, nxt.fi, dep[u]);
}
}
int best_path(int N, int K, int H[][2], int L[]){
_K = K;
for(int i = 0; i < N - 1; i++) ae(H[i][0], H[i][1], L[i]);
dfs(0, -1);
if(ans != INF) return ans;
else return -1;
}
