#include<race.h>
#include<vector>
#include<set>
using namespace std;
int nrPaths;
set<pair<int,int> > S[200005];
vector<pair<int,int> > A[200005];
int HPath[200005],Dist[200005],Lev[200005];
int dfs(int nod, int p, int L)
{
int rez=1000000000;
for(auto other:A[nod])
{
if(other.first==p)
continue;
Dist[other.first]=Dist[nod]+other.second;
Lev[other.first]=Lev[nod]+1;
rez=min(rez,dfs(other.first,nod,L));
if(S[HPath[other.first]].size()>S[HPath[nod]].size())
HPath[nod]=HPath[other.first];
}
if(HPath[nod]==0)
HPath[nod]=++nrPaths;
int path=HPath[nod];
for(auto other:A[nod])
{
if(other.first==p || path==HPath[other.first])
continue;
for(auto el:S[HPath[other.first]])
{
int dist=L-(el.first-Dist[nod])+Dist[nod];
if(dist>Dist[nod])
{
set<pair<int,int> >::iterator it=S[path].lower_bound({dist,0});
if(it!=S[path].end() && (*it).first==dist)
rez=min(rez,(*it).second+el.second-2*Lev[nod]);
}
set<pair<int,int> >::iterator it=S[path].lower_bound({el.first,0});
if(it!=S[path].end() && (*it).first==el.first)
{
if(el.second<(*it).second)
{
S[path].erase(it);
S[path].insert(el);
}
}
else
S[path].insert(el);
}
}
S[path].insert({Dist[nod],Lev[nod]});
set<pair<int,int> >::iterator it=S[path].lower_bound({Dist[nod]+L,0});
if(it!=S[path].end() && (*it).first==Dist[nod]+L)
rez=min(rez,(*it).second-Lev[nod]);
return rez;
}
int best_path(int n, int k, int E[][2], int L[])
{
for(int i=0; i<=n-2; i++)
{
A[E[i][0]].push_back({E[i][1],L[i]});
A[E[i][1]].push_back({E[i][0],L[i]});
}
int rez=dfs(0,-1,k);
if(rez==1000000000)
rez=-1;
return rez;
}
