#include "race.h"
#include <vector>
#include <utility>
#include <map>
using namespace std;
long long ans=1000000000;
map < long long , long long > small;
vector < pair < long long , long long > > t;
vector < pair < pair < long long , long long > , long long > > Next[200005];
vector < long long > vis;
long long how[200005];
long long big[200005];
long long tt=0;
long long K;
void F(long long fa,long long here,long long dis,long long deg,long long K)
{
if(small.find(K-dis)!=small.end()) ans=min(ans,small[K-dis]+deg);
if(dis>K) return ;
t.push_back(make_pair(K,dis));
for(auto i:Next[here]) if(i.first.first!=fa&&i.second) F(here,i.first.first,dis+i.first.second,deg+1,K);
}
void DFS2(long long fa,long long here)
{
big[here]=0;
how[here]=1;
tt++;
vis.push_back(here);
for(auto i:Next[here])
{
if(i.first.first!=fa&&i.second)
{
DFS2(here,i.first.first);
big[here]=max(big[here],how[i.first.first]);
how[here]+=how[i.first.first];
}
}
}
void DFS(long long here)
{
vector < int > ttt;
vis.clear();
DFS2(-1,here);
tt=0;
long long center;
for(auto i:vis) if(max(big[i],tt-how[i])<=tt/2+1) center=i;
vis.clear();
small.clear();
small[0]=0;
for(auto &i:Next[center])
{
if(i.second)
{
ttt.push_back(i.first.first);
i.second=0;
t.clear();
F(here,i.first.first,i.first.second,1,K);
for(auto j:t)
{
if(small.find(j.first)==small.end()) small[j.first]=j.second;
else small[j.first]=min(small[j.first],j.second);
}
}
}
for(auto i:ttt) DFS(i);
}
int best_path(int N, int K, int H[][2], int L[])
{
::K=K;
int i;
for(i=0;i<N-1;i++)
{
Next[H[i][0]].push_back(make_pair(make_pair((long long) H[i][1],(long long) L[i]),1));
Next[H[i][1]].push_back(make_pair(make_pair((long long) H[i][0],(long long) L[i]),1));
}
DFS(0);
if(ans==1000000000) ans=-1;
return (int) ans;
}
