#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sp << ' ' <<
#define nl << '\n'
#define v e.first
#define w e.second
#include "race.h"
const int MAXN = 2e5, INF = 1e9;
int ans = INF, k;
vector<vector<pair<int, int>>> g(MAXN);
vector<int> s(MAXN), len(1000001, INF);
vector<bool> r(MAXN);
vector<int> toUpdate;
int calcSize(int u, int p){
s[u] = 1;
for(auto &e : g[u]) if(v != p and !r[v]) s[u] += calcSize(v, u);
return s[u];
}
void calcDist(int u, int p, int currLength, int currDist, int root){
if(currDist>k) return;
if(len[currDist]==INF) toUpdate.push_back(currDist);
len[currDist] = min(len[currDist], currLength);
for(auto &e : g[u]) if(v != p and !r[v]) calcDist(v, u, currLength+1, currDist+w, root);
}
void dfs(int u, int p, int currLength, int currDist, int root){
if(currDist>k) return;
ans = min(ans, len[k-currDist] + currLength);
for(auto &e : g[u]) if(v != p and !r[v]) dfs(v, u, currLength+1, currDist+w, root);
}
int find(int u, int p, int treeSize){
for(auto &e : g[u]) if(v != p and !r[v] and s[v] > treeSize/2) return find(v, u, treeSize);
return u;
}
void decompose(int u){
int c = find(u, u, calcSize(u, u));
r[c] = true;
for(auto &e : g[c]){
if(r[v]) continue;
dfs(v, c, 1, w, c);
calcDist(v, c, 1, w, c);
}
ans = min(ans, len[k]);
while(!toUpdate.empty()) len[toUpdate.back()] = INF, toUpdate.pop_back();
for(auto &e : g[c]) if(!r[v]) decompose(v);
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
for(int i=0; i<N-1; ++i){
g[H[i][0]].emplace_back(H[i][1], L[i]);
g[H[i][1]].emplace_back(H[i][0], L[i]);
}
decompose(0);
if(ans>N) ans = -1;
return ans;
}
