#include "race.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
int ans=1e9;
int k;
vector<pair<int,int>>adj[200005];
ll dep[200005];
int dis[200005];
map<ll,int> dfs(int u,int p)
{
map<ll,int>y;
y[dep[u]]=dis[u];
for(auto x:adj[u])
{
if(x.F!=p)
{
dep[x.F]=dep[u]+x.S;
dis[x.F]=dis[u]+1;
map<ll,int>j=dfs(x.F,u);
if(j.size()>=y.size())
swap(j,y);
for(auto f:j)
{
if(f.F-dep[u]<=k&&y.count(k-f.F+2*dep[u]))
{
ans=min(ans,y[k-f.F+2*dep[u]]+f.S-2*dis[u]);
}
}
for(auto g:j)
{
if(y[g.F])
y[g.F]=min(y[g.F],g.S);
else
y[g.F]=g.S;
}
}
}
return y;
}
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]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
dis[0]=1;
dfs(0,-1);
if(ans==1e9)
ans=-1;
return ans;
}
