#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back
void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}
template<typename T,typename V>
void PRINT(pair<T,V>& x){
cerr<<"{";
PRINT(x.fi);
cerr<<",";
PRINT(x.se);
cerr<<"}";
}
template<typename T>
void PRINT(T &x){
int id=0;
cerr<<"{";
for(auto _i:x){
cerr<<(id++ ? "," : "");
PRINT(_i);
}
cerr<<"}";
}
void _PRINT(){
cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
PRINT(h);
if(sizeof...(t)) cerr<<", ";
_PRINT(t...);
}
#ifndef ONLINE_JUDGE
#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)
#endif
vector<vector<pii>> adj;
vector<bool> vis;
vector<int> siz;
vector<int> dub,dubw;
unordered_map<int,int> global,local;
int grana,W,res,T,H;
void DfsDecompose(int node,int par){
siz[node]=1;
for(pii e:adj[node]){
if(!vis[e.fi] && e.fi!=par){
DfsDecompose(e.fi,node);
siz[node]+=siz[e.fi];
}
}
}
void Dfs(int node,int par,int w){
if(par==-1){
dub[node]=1;
dubw[node]=0;
}
else{
dub[node]=dub[par]+1;
dubw[node]=dubw[par]+w;
}
T=dubw[node]+grana,H=dub[node];
//Debug(node,T,H);
local[T]=min((local.count(T) ? local[T] : INF),H);
global[T]=min((global.count(T) ? global[T] : INF),H+1);
//Debug(local[T]+(global.count(W-T) ? global[W-T] : INF));
res=min(res,local[T]+(global.count(W-T) ? global[W-T] : INF));
//Debug(res);
//Debug(adj[node]);
for(pii e:adj[node]){
if(!vis[e.fi] && e.fi!=par){
Dfs(e.fi,node,e.se);
}
}
}
int Find(int node,int par,int n){
for(pii e:adj[node]){
if(!vis[e.fi] && e.fi!=par && siz[e.fi]>n/2){
return Find(e.fi,node,n);
}
}
return node;
}
int Find(int node){
DfsDecompose(node,-1);
node=Find(node,-1,siz[node]);
return node;
}
void Decompose(int node){
node=Find(node); vis[node]=true; //Debug(node);
global.clear();
for(pii e:adj[node]){
if(!vis[e.fi]){
local.clear();
grana=e.se;
Dfs(e.fi,-1,0);
//Debug(global,local);
}
}
for(pii e:adj[node]){
if(!vis[e.fi]) Decompose(e.fi);
}
}
int best_path(int N, int K, int H[][2], int L[]){
//Debug(N,K);
adj.resize(N+1); siz.resize(N+1); vis.resize(N+1); dub.resize(N+1); dubw.resize(N+1);
W=K;
for(int i=0;i<N-1;i++){
int u=H[i][0],v=H[i][1],w=L[i];
adj[u].pb({v,w});
adj[v].pb({u,w});
}
res=INF;
Decompose(0);
return (res>=INF ? -1 : res-1);
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/
