#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define len(a) ((int)a.size())
const int N = 200005;
int ans = -1;
vector< pair<int, int> > g[N];
int sz[N], all, k;
bool used[N];
void update(int nans){
if(ans == -1 || nans < ans){
ans = nans;
}
}
void sizes(int v, int p){
sz[v] = 1;
for(int i = 0; i < len(g[v]); i++){
int to = g[v][i].first;
if(to == p || used[to]) continue;
sizes(to, v);
sz[v] += sz[to];
}
}
int cfind(int v, int p){
if(p == -1){
all = sz[v];
}
for(int i = 0; i < len(g[v]); i++){
int to = g[v][i].first;
if(to == p || used[to]) continue;
if(sz[to] > (all / 2)) {
return cfind(to, v);
}
}
return v;
}
vector< pair<int, int> > mas;
map<int, int> mp;
void solve(int v, int p, int d, int l){
if(p != -1){
mas.push_back(make_pair(d, l));
}
for(int i = 0; i < len(g[v]); i++){
int to = g[v][i].first, len = g[v][i].second;
if(to == p || used[to]) continue;
solve(to, v, d + 1, l + len);
if(p == -1){
for(int j = 0; j < len(mas); j++){
int L = mas[j].second;
int D = mas[j].first;
if(L > k) continue;
if(L == k) {
update(D);
}
else if (mp.find(k - L) != mp.end()){
update(mp[k - L] + D);
}
}
for(int j = 0; j < len(mas); j++){
int dep = mas[j].first, dis = mas[j].second;
if(dis > k) continue;
if(mp.find(dis) != mp.end()){
mp[dis] = min(mp[dis], dep);
}
else {
mp[dis] = dep;
}
}
mas.clear();
}
}
}
void centroid_decomposition(){
queue<int> q;
q.push(1);
while(!q.empty()){
int v = q.front();
q.pop();
sizes(v, -1);
v = cfind(v, -1);
sizes(v, -1);
mp.clear();
solve(v, -1, 0, 0);
used[v] = true;
for(int i = 0; i < len(g[v]); i++){
int to = g[v][i].first;
if(used[to]) continue;
if(sz[to] == 1) continue;
q.push(to);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for(int i = 0; i < N - 1; i++){
int u = H[i][0], v = H[i][1], d = L[i];
g[u].push_back(make_pair(v, d));
g[v].push_back(make_pair(u, d));
}
centroid_decomposition();
return ans;
}
//int main(){
// int L[] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
// int H[][2] = {{0, 1}, {0, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 6}, {6, 7}, {6, 8}, {8, 9}, {8, 10}};
//
// cout << best_path(11, 12, H, L) << endl;
// return 0;
//}
