#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define oo 1e9
const int MAX = 2e5 + 5;
vector<pii> g[MAX];
int n, k;
map<ll, int> mp[MAX];
int ans = oo;
void dfs(int node, int p, ll d, int h){
for(pii to : g[node]){
if(to.first == p) continue;
dfs(to.first, node, d + to.second, h + 1);
if(mp[to.first].size() > mp[node].size()){
swap(mp[node], mp[to.first]);
}
}
for(pii to : g[node]){
if(to.first == p) continue;
for(auto a : mp[to.first]){
if(!a.second) continue;
ll need = d + (k - (a.first - d));
if(need <= d || mp[node].find(need) == mp[node].end()) continue;
ans = min(ans, (a.second - h) + (mp[node][need] - h));
}
for(auto a : mp[to.first]){
if(!a.second) continue;
if(mp[node].find(a.first) == mp[node].end()){
mp[node][a.first] = a.second;
}
else{
mp[node][a.first] = min(a.second, mp[node][a.first]);
}
}
}
mp[node][d] = h;
if(mp[node].find(d + k) != mp[node].end()){
ans = min(ans, mp[node][d + k] - h);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
for(int i = 0; i < n; i++){
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
dfs(0, 0, 0, 0);
if(ans == oo) return -1;
return ans;
}
