#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int MAXN=2e5+5,MAXK=1e6+5;
#define ll long long
#define pb push_back
vector<pair<int,int>> adj[MAXN];
int sz[MAXN],k;
bool removed[MAXN];
void subtree_size(int node,int par){
sz[node]=1;
for(auto i:adj[node]){
if(i.first==par || removed[i.first])continue;
subtree_size(i.first,node);
sz[node]+=sz[i.first];
}
}
int centroid(int node,int par,int tot){
for(auto i:adj[node]){
if(i.first==par || removed[i.first])continue;
if(sz[i.first]*2>tot)return centroid(i.first,node,tot);
}
return node;
}
pair<int,int> best[MAXK][2];
vector<ll> uniq;
void dfs2(int node,int par,int og,int sum=0,int length=0){
if(sum<=k) {
uniq.pb(sum);
if (best[sum][0].second == og) {
best[sum][1] = min(best[sum][1], {length, og});
} else if (best[sum][1].second == og) {
best[sum][0] = min(best[sum][0], {length, og});
} else {
if (best[sum][0].first > length)best[sum][0] = {length, og};
else best[sum][1] = min(best[sum][1], {length, og});
}
}
bool flag=(og==-1);
for(auto i:adj[node]){
if(i.first==par || removed[i.first])continue;
dfs2(i.first,node,(flag?i.first:og),sum+i.second,length+1);
}
}
int ans=2e9;
void dfs(int node){
subtree_size(node,-1);
int c=centroid(node,-1,sz[node]);
dfs2(c,-1,-1);
for(auto i:uniq){
int x=i,req=k-i;
if(req<0)continue;
ans=min(ans,best[x][0].first+best[req][0].first);
}
for(auto i:uniq){
best[i][0]={2e8,2e8};
best[i][1]={2e8,2e8};
}
removed[c]=1;
for(auto i:adj[c]){
if(!removed[i.first])dfs(i.first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k=K;
for(int i=0;i<N-1;i++){
adj[H[i][0]].pb({H[i][1],L[i]});
adj[H[i][1]].pb({H[i][0],L[i]});
}
for(int i=0;i<MAXK;i++){
best[i][0]={2e8,2e8};
best[i][1]={2e8,2e8};
}
subtree_size(0,-1);
dfs(0);
if(ans>N)return -1;
return ans;
}
