#include "race.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e5+5;
vector<ii> adj[nx];
bool del[nx];
int sz[nx], cnt[1000005], ans=inf, lim;
ll dep[nx];
int go(int p, int u)
{
sz[u]=1;
for(auto it:adj[u])
{
int v=it.fi;
if(v!=p && !del[v])
sz[u]+=go(u, v);
}
return sz[u];
}
int centroid(int p, int u, int tre)
{
for(auto it:adj[u])
{
int v=it.fi;
if(v!=p && !del[v] && sz[v]>tre/2)
return centroid(u, v, tre);
}
return u;
}
void dfs(int p, int u, int hi, bool ok)
{
if(ok==0)
{
if(dep[u]<=lim)
ans=min(ans, hi+cnt[lim-dep[u]]);
}
else if(dep[u]<=lim) cnt[dep[u]]=min(cnt[dep[u]], hi);
for(auto it:adj[u])
{
int v=it.fi;
if(v!=p && !del[v])
dep[v]=dep[u]+it.se, dfs(u, v, hi+1, ok);
}
}
void dfs1(int p, int u)
{
if(dep[u]<=lim) cnt[dep[u]]=inf;
for(auto it:adj[u])
if(it.fi!=p && !del[it.fi])
dfs1(u, it.fi);
}
void build(int u)
{
int root=centroid(0, u, go(0, u));
dep[root]=0;
for(auto it:adj[root])
{
int v=it.fi;
if(!del[v])
dep[v]=it.se, dfs(root, v, 1, 0), dfs(root, v, 1, 1);
}
ans=min(ans, cnt[lim]);
dfs1(0, root);
del[root]=1;
for(auto it:adj[root])
if(!del[it.fi])
build(it.fi);
}
int best_path(int n, int k, int h[][2], int l[])
{
lim=k;
for(int i = 0; i < n; i++)
adj[i].clear();
for(int i = 0; i < n-1; i++)
adj[h[i][0]].emplace_back(h[i][1], l[i]), adj[h[i][1]].emplace_back(h[i][0], l[i]);
for(int i = 0; i <= k; i++)
cnt[i]=inf;
build(0);
if(ans==inf) ans=-1;
return ans;
}
// int a[nx][2], b[nx];
// int main()
// {
// a[0][0]=0, a[0][1]=1;
// a[1][0]=1, a[1][1]=2;
// a[2][0]=1, a[2][1]=3;
// int b[nx];
// b[0]=1, b[1]=2, b[2]=4;
// cout<<best_path(4, 3, a, b);
// }
