#include "race.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=2e5+9;
vector<int> tree[mxn];
vector<int> cost[mxn];
int subsz[mxn];
int centroidMarked[mxn]={};
int level[mxn]={};
int pa[18][mxn];
ll dist[18][mxn];
int parent[mxn]={};
int ans=mxn;
int K;
vector<int> centree[mxn];
void initLCA(int n)
{
for(int i=1;i<18;i++)
{
for(int j=0;j<n;j++)
{
if(pa[i-1][j]!=-1)
{
pa[i][j]=pa[i-1][pa[i-1][j]];
dist[i][j]=dist[i-1][j]+dist[i-1][pa[i-1][j]];
}
}
}
}
int findlca(int u,int v)
{
if(level[u]<level[v])swap(u,v);
int diff=level[u]-level[v];
for(int i=0;i<18;i++)
{
if((diff>>i)&1)u=pa[i][u];
}
if(u==v)return u;
for(int i=17;i>=0;i--)
{
if(pa[i][u]!=pa[i][v])
{
u=pa[i][u];
v=pa[i][v];
}
}
return pa[0][u];
}
int pathn(int u,int v)
{
int lca=findlca(u,v);
return level[u]-level[lca]+level[v]-level[lca];
}
ll td(int u,int lca)
{
int diff=level[u]-level[lca];
ll r=0;
for(int i=0;i<18;i++)
{
if((diff>>i)&1)
{
r+=dist[i][u];
u=pa[i][u];
}
}
return r;
}
ll getdist(int u,int v)
{
int lca=findlca(u,v);
return td(u,lca)+td(v,lca);
}
void dfs(int cur,int prev)
{
subsz[cur]=1;
for(int i:tree[cur])
{
if(i!=prev && !centroidMarked[i])
{
dfs(i,cur);
subsz[cur]+=subsz[i];
}
}
}
int getCentroid(int cur,int prev,int sz)
{
bool isC=true;
int hc=-1;
for(int i:tree[cur])
{
if(i!=prev && !centroidMarked[i] && subsz[i]>sz)
{
hc=i;
isC=false;
break;
}
}
if(isC && subsz[cur]>=sz)return cur;
return getCentroid(hc,cur,sz);
}
int getCentroid(int src)
{
dfs(src,-1);
int c=getCentroid(src,-1,subsz[src]/2);
centroidMarked[c]=1;
return c;
}
int build(int root)
{
int c=getCentroid(root);
for(int i:tree[c])
{
if(!centroidMarked[i])
{
int d=build(i);
centree[c].push_back(d);
parent[d]=c;
}
}
return c;
}
void dfs2(int cur,int prev,int cst)
{
level[cur]=level[prev]+1;
pa[0][cur]=prev;
dist[0][cur]=cst;
for(int i=0;i<tree[cur].size();i++)
{
int v=tree[cur][i];
if(v!=prev)
{
dfs2(v,cur,cost[cur][i]);
}
}
}
map<int,int> mp[mxn];
void pans(int cur,int rt)
{
int d=pathn(cur,rt);
ll dst=getdist(cur,rt);
if(dst<=K)
{
if(mp[rt].find(K-dst)!=mp[rt].end())
{
ans=min(ans,(d+mp[rt][K-dst]));
}
}
for(int i:centree[cur])pans(i,rt);
}
void update(int cur,int rt)
{
int d=pathn(cur,rt);
ll dst=getdist(cur,rt);
if(dst<=K)
{
if(mp[rt].find(dst)==mp[rt].end())mp[rt][dst]=d;
else mp[rt][dst]=min(d,mp[rt][dst]);
}
for(int i:centree[cur])update(i,rt);
}
void df(int cur)
{
for(int i:centree[cur])
{
pans(i,cur);
update(i,cur);
}
}
int best_path(int N, int k, int H[][2], int L[])
{
K=k;
for(int i=0;i<N-1;i++)
{
tree[H[i][0]].push_back(H[i][1]);
tree[H[i][1]].push_back(H[i][0]);
cost[H[i][0]].push_back(L[i]);
cost[H[i][1]].push_back(L[i]);
}
memset(pa,-1,sizeof(pa));
dfs2(0,0,0);
initLCA(N);
int r=build(0);
for(int i=0;i<N;i++)df(i);
return ans==mxn?-1:ans;
}
