#include <bits/stdc++.h>
#include "race.h"
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<ll, pii> ipii;
const ll MAXN = 2e5+10;
const ll INF = 2e18;
const ll MOD = 1e9+7;
ll n, k;
vector <pii> adj[MAXN];
ll sub[MAXN], big[MAXN], dep[MAXN], off[MAXN];
ll ans = INF;
map <ll, ll> *m[MAXN];
void dfs(ll nw, ll par){
sub[nw] = 1; dep[nw] = dep[par]+1;
big[nw] = n+1;
for(auto ed : adj[nw]){
ll nx = ed.fi;
if(nx == par) continue;
dfs(nx, nw);
if(sub[nx] > sub[big[nw]]) big[nw] = nx;
sub[nw] += sub[nx];
}
}
void upd(ll nw, ll len, ll depth){
if((*m[nw]).find(len) == (*m[nw]).end()) (*m[nw])[len] = depth;
else (*m[nw])[len] = min((*m[nw])[len], depth);
}
void dsu(ll nw, ll par){
if(adj[nw].size() == 1 && par != 0){ //leaf
m[nw] = new map<ll,ll>;
upd(nw, 0, dep[nw]);
return;
}
for(auto ed : adj[nw]){
ll nx = ed.fi; ll wei = ed.se;
if(nx == par) continue;
dsu(nx, nw); //dfs
off[nx] += wei; //nambah edge
}
m[nw] = m[big[nw]]; off[nw] = off[big[nw]]; //offset + map sama
upd(nw, -off[nw], dep[nw]);
for(auto ed : adj[nw]){
ll nx = ed.fi; ll wei = ed.se;
if(nx == par || nx == big[nw]) continue;
// cek inside
for(auto in : (*m[nx])){
ll len = in.fi; ll depth = in.se;
len += off[nx]; //keluar, nambahin
if(len > k || (*m[nw]).find(k-len-off[nw]) == (*m[nw]).end() ) continue; //gk ad
ans = min(ans, (*m[nw])[k-len-off[nw]] + depth - 2*dep[nw]);
//cek dalem, kurangin
}
// merge (*m[nx])
for(auto in : (*m[nx])){
ll len = in.fi; ll depth = in.se;
len += off[nx];
if( (*m[nw]).find(len-off[nw]) == (*m[nw]).end() ) (*m[nw])[len-off[nw]] = depth;
else (*m[nw])[len-off[nw]] = min((*m[nw])[len-off[nw]], depth);
}
}
// cout << nw << ' ' << off[nw] << "off\n";
// for(auto in : (*m[nw])){
// cout << in.fi << ' '<< in.se << '\n';
// }
//cek dalem
if( (*m[nw]).find(k-off[nw]) != (*m[nw]).end() )
ans = min(ans, (*m[nw])[k-off[nw]] - dep[nw]);
}
int best_path(int N, int K, int H[][2], int L[]){
n = N; k = K;
for(ll i=0; i<n-1; i++){
adj[H[i][0]+1].pb({H[i][1]+1, L[i]});
adj[H[i][1]+1].pb({H[i][0]+1, L[i]});
}
// 1-n
dfs(1, 0);
dsu(1, 0);
return (ans==INF ? -1 : ans);
}
