# include <iostream>
# include <vector>
# include <map>
# include "race.h"
//# include "grader.cpp"
using namespace std;
const int INF=1e9;
const int MAX=2e5+11;
int n,k;
vector<pair<int, long long>> adj[MAX];
int sz[MAX];
bool kill[MAX];
void dfs_sz(int curr, int par)
{
sz[curr]=1;
for(pair<int, long long> nxt: adj[curr])
{
if(nxt.first==par or kill[nxt.first]) continue;
dfs_sz(nxt.first,curr);
sz[curr]+=sz[nxt.first];
}
}
int get_centroid(int curr, int par, int N)
{
for(pair<int, long long> nxt: adj[curr])
{
if(nxt.first==par or kill[nxt.first]) continue;
if(sz[nxt.first]*2>N) return get_centroid(nxt.first,curr,N);
}
return curr;
}
int ans=INF;
map<long long, int> mapi;
void add(long long x, int cnt)
{
if(mapi.find(x)==mapi.end()) mapi[x]=cnt;
else mapi[x]=min(mapi[x],cnt);
}
void dfs_ans(int curr, int par, long long dist, int cnt)
{
if(mapi.find(k-dist)!=mapi.end()) ans=min(ans,cnt+mapi[k-dist]);
for(pair<int, long long> nxt: adj[curr])
{
if(nxt.first==par or kill[nxt.first]) continue;
dfs_ans(nxt.first,curr,dist+nxt.second,cnt+1);
}
}
void dfs_fill(int curr, int par, long long dist, int cnt)
{
add(dist,cnt);
for(pair<int, long long> nxt: adj[curr])
{
if(nxt.first==par or kill[nxt.first]) continue;
dfs_fill(nxt.first,curr,dist+nxt.second,cnt+1);
}
}
void cd(int curr)
{
dfs_sz(curr,-1);
curr=get_centroid(curr,-1,sz[curr]);
add(0,0);
for(pair<int, long long> nxt: adj[curr])
{
if(kill[nxt.first]) continue;
dfs_ans(nxt.first,curr,nxt.second,1);
dfs_fill(nxt.first,curr,nxt.second,1);
}
mapi.clear();
kill[curr]=1;
for(pair<int, long long> nxt: adj[curr])
{
if(kill[nxt.first]) continue;
cd(nxt.first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;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]});
}
cd(0);
if(ans==INF) ans=-1;
return ans;
}
/*
3 3
0 1 1
1 2 1
-1
*/
