#include "race.h"
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;
using pii = pair<int,int>;
using ll = long long;
int const N1 = 2e5+10;
int const N2 = 1e6+10;
int const INF = 1e9+10;
int rem[N1];
vector<pii> adj[N1];
int nodecnt[N1];
int cnt[N2];
int V;
int ans = INF;
void getsize(int n,int p){
nodecnt[n] = 1;
for(auto [l,k]:adj[n]){
if(rem[k] || k == p) continue;
getsize(k,n);
nodecnt[n] += nodecnt[k];
}
}
int getcentroid(int full,int n,int p){
for(auto [l,k]:adj[n]){
if(k == p || rem[k]) continue;
if(nodecnt[k] > full/2) return getcentroid(full,k,n);
}
return n;
}
void getdist(int n,int p,int curdist,int curcnt,vector<pii> &dist){
if(curdist > V) return;
dist.emplace_back(curdist,curcnt);
for(auto [l,k]:adj[n]){
if(rem[k] || k == p) continue;
getdist(k,n,curdist+l,curcnt+1,dist);
}
}
void process(int n){
vector<int> used;
for(auto [l,k]:adj[n]){
if(rem[k]) continue;
vector<pii> dist;
getdist(k,n,l,1,dist);
for(auto [a,b]:dist){
if(cnt[V-a]){
ans = min(ans,cnt[V-a]+b);
}
}
for(auto [a,b]:dist){
if(cnt[a] > b){
used.emplace_back(a);
cnt[a] = b;
}
}
}
for(auto k:used){
cnt[k] = INF;
}
}
void dfs(int n,int p){
getsize(n,p);
int cen = getcentroid(nodecnt[n],n,p);
rem[cen] = 1;
process(cen);
for(auto [l,k]:adj[cen]){
if(k == p || rem[k]) continue;
dfs(k,cen);
}
}
void reset(){
ans = INF;
V = 0;
for(int i{};i < N2;i++){
cnt[i] = INF;
}
memset(nodecnt,0,sizeof nodecnt);
memset(rem,0,sizeof rem);
for(auto k:adj){
k.clear();
}
}
int best_path(int N, int K, int H[][2], int L[])
{
reset();
V = K;
for(int i{};i < N-1;i++){
int u = H[i][0];
int v = H[i][1];
int w = L[i];
adj[u].emplace_back(w,v);
adj[v].emplace_back(w,u);
}
dfs(0,0);
if(ans == INF) return -1;
return ans;
}
