#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
int n,k,par[mxn],sub[mxn],color[mxn],sz,first,ans=1e9;
map<int,int>global,local;
vector<pii>vt[mxn];
void calc(int u,int p){
sz++;
sub[u]=1;
for(pii pp:vt[u]){
int v=pp.F;
if(v!=p&&!color[v]){
calc(v,u);
sub[u]+=sub[v];
}
}
}
int find_centroid(int u,int p){
for(pii pp:vt[u]){
int v=pp.F;
if(v==p) continue;
if(sub[v]*2>sz&&!color[v]){
return find_centroid(v,u);
}
}
return u;
}
void dfs(int u,int p,ll dis,int dep){
if(dis==k) ans=min(ans,dep);
if(dep>0&&dis<=k){
if(global[k-dis]!=0){
ans=min(ans,dep+global[k-dis]);
}
if(local[dis]==0){
local[dis]=dep;
}
else{
local[dis]=min(local[dis],dep);
}
}
for(pii pp:vt[u]){
int v=pp.F,len=pp.S;
if(v!=p&&!color[v]){
if(dep==0) local.clear();
dfs(v,u,dis+len,dep+1);
if(dep==0){
for(auto it=local.begin();it!=local.end();it++){
int x=it->F;
int y=it->S;
if(global[x]==0){
global[x]=y;
}
else{
global[x]=min(global[x],y);
}
}
}
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N,k=K;
for(int i=0;i<n-1;i++){
int u=H[i][0]+1,v=H[i][1]+1;
vt[u].pb({v,L[i]});
vt[v].pb({u,L[i]});
if(L[i]==k) return 1;
}
for(int id=1;id<=20;id++){
for(int i=1;i<=n;i++){
if(!color[i]){
sz=0;
calc(i,-1);
int node=find_centroid(i,-1);
color[node]=1;
global.clear();
local.clear();
dfs(node,-1,0,0);
}
}
}
if(ans==1e9) return -1;
return ans;
}
