#include<bits/stdc++.h>
#include "race.h"
using namespace std;
int i, j, ans, tot, t, k, total, len, sz[500007]; long long int dis;
multiset<int> s[1000007];
vector<pair<int, int>> tem;
vector<pair<int, int>> v[500007];
bool c[500007];
void dfs(int cu, int pa){
sz[cu] = 1;
for(pair<int, int> z: v[cu]){
if(c[z.first] == 0 || z.first == pa) continue;
dfs(z.first, cu); sz[cu] += sz[z.first];
}
}
int dfs_cen(int cu, int pa){
for(pair<int, int> z: v[cu]){
if(c[z.first] == 0 || z.first == pa) continue;
if(sz[z.first] > tot/2) return dfs_cen(z.first, cu);
}
return cu;
}
void dfsc(int cu, int pa){
if(dis <= k) s[dis].insert(len);
len++;
for(pair<int, int> z: v[cu]){
if(c[z.first] == 0 || z.first == pa) continue;
dis += z.second;
dfsc(z.first, cu);
dis -= z.second;
} len--;
}
void dfsc2(int cu, int pa){
if(dis <= k) s[dis].clear();
for(pair<int, int> z: v[cu]){
if(c[z.first] == 0 || z.first == pa) continue;
dis += z.second;
dfsc2(z.first, cu);
dis -= z.second;
}
}
void dfsgetp(int cu, int pa){
if(dis <= k) tem.push_back({dis, len});
len++;
for(pair<int, int> z: v[cu]){
if(c[z.first] == 0 || z.first == pa) continue;
dis += z.second;
dfsgetp(z.first, cu);
dis -= z.second;
} len--;
}
void get(int in){
dfs(in, -1); tot = sz[in];
int cen = dfs_cen(in, -1);
dis = 0; len = 0; dfsc(cen, -1);
for(pair<int, int> z: v[cen]){
dis = z.second; len = 1;
dfsgetp(z.first, cen);
for(pair<int, int> x: tem) s[x.first].erase(s[x.first].find(x.second));
for(pair<int, int> x: tem){
if(!s[k-x.first].empty())
ans = min(ans, x.second+(*s[k-x.first].begin()));
}
for(pair<int, int> x: tem) s[x.first].insert(x.second);
tem.clear();
}
dis = 0; dfsc2(cen, -1);
c[cen] = 0;
for(pair<int, int> z: v[in]) if(c[z.first]) get(z.first);
}
int best_path(int N, int K, int H[][2], int L[]){
ans = 1e9; k = K;
for( i = 0; i < N; i++) c[i] = 1;
for( i = 0; i < N-1; i++){
v[H[i][0]].push_back({H[i][1], L[i]});
v[H[i][1]].push_back({H[i][0], L[i]});
}
get(0);
if(ans == 1e9) ans = -1;
return ans;
}
