#include "race.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N=2e5+5;
vector< pair<int,int> > adj[N];
int n,k, ans=(1<<30);
int sz[N], del[N], nn;
void dfs0(int node, int pa=-1)
{
sz[node]=1;
nn++;
//for(auto it:adj[node])
for(int i=0;i<adj[node].size();i++)
{
auto it=adj[node][i];
if(del[it.F])
{
swap(adj[node][i],adj[node].back());
adj[node].pop_back();
i--; continue;
}
if(del[it.F] || it.F==pa) continue;
dfs0(it.F, node);
sz[node]+=sz[it.F];
}
}
int find_cent(int node,int pa=-1)
{
for(auto it:adj[node])
{
if(del[it.F]||it.F==pa) continue;
if(sz[it.F]>nn/2) return find_cent(it.F, node);
}
return node;
}
map<long long,multiset<int>> co;
void dfs1(int node, int pa, long long len, int h, int add)
{
if(add)
co[len].insert(h);
else
co[len].erase(co[len].find(h));
for(auto it:adj[node])
{
if(del[it.F]||it.F==pa) continue;
dfs1(it.F, node, len+it.S, h+1, add);
}
}
void dfs2(int node, int pa, long long len, int h)
{
if(co.count(k-len))
{
if(co[k-len].size())
ans=min(ans,h+(*co[k-len].begin()));
}
for(auto it:adj[node])
{
if(del[it.F]||it.F==pa) continue;
dfs2(it.F, node, len+it.S, h+1);
}
}
void dfs_cent(int root)
{
nn=0; co.clear();
dfs0(root);
int cent=find_cent(root);
dfs1(cent, -1, 0, 0, 1);
for(auto it:adj[cent])
{
if(del[it.F]) continue;
dfs1(it.F, cent, it.S, 1, 0);
dfs2(it.F, cent, it.S, 1);
}
del[cent]=1;
for(auto it:adj[cent])
{
if(!del[it.F])
dfs_cent(it.F);
}
}
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]});
}
dfs_cent(0);
return (ans==(1<<30)?-1:ans);
}
