#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){
ans = nans;
return;
}
ans = min(ans, nans);
}
void sizes(int v, int p){
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];
}
sz[v]++;
}
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;
if(l > k) break;
if(l == k) {
update(d);
}
else if (mp.find(k - l) != mp.end()){
update(mp[k - l] + d);
}
solve(to, v, d + 1, l + len);
if(p == -1){
for(int j = 0; j < len(mas); j++){
int dep = mas[i].first, dis = mas[i].second;
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);
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; 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;
//}
