#include<bits/stdc++.h>
// #include "race.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define endl '\n'
int k, cn=0, sub[200005], ans=INT_MAX, pref[200005], depth[200005];
vector<pii> adj[200005];
bool deleted[200005];
map<int, int> mn;
void dfs(int x, int p=-1)
{
cn++;
sub[x]=1;
for(auto[i, _] : adj[x])
{
if(!deleted[i]&&i!=p) {dfs(i, x);sub[x]+=sub[i];}
}
}
int centr(int x, int p=-1)
{
for(auto[i, _] : adj[x])
{
if(i!=p&&!deleted[i]&&sub[i]>cn/2) return centr(i, x);
}
return x;
}
void init(int x, int p=-1)
{
for(auto[i, w] : adj[x])
{
if(i==p||deleted[i]) continue;
pref[i]=pref[x]+w;
depth[i]=depth[x]+1;
init(i, x);
}
}
void query(int x, int p=-1)
{
if(pref[x]==k) ans=min(ans, depth[x]);
if(mn[k-pref[x]]!=NULL) ans=min(ans, mn[k-pref[x]]+depth[x]);
for(auto[i, _]:adj[x])
{
if(i!=p&&!deleted[i]) query(i, x);
}
}
void update(int x, int p=-1)
{
mn[pref[x]]=min(mn[pref[x]], depth[x]);
for(auto[i, _]:adj[x])
{
if(i!=p&&!deleted[i]) update(i, x);
}
}
void solve(int x)
{
pref[x]=0;
depth[x]=0;
init(x);
for(auto[i, _] : adj[x])
{
if(deleted[i]) continue;
query(i);
update(i);
}
}
void decompose(int v)
{
cn=0;
dfs(v);
int cen=centr(v);
solve(cen);
deleted[cen]=1;
for(auto[i, _] : adj[cen])
{
if(!deleted[i]) decompose(i);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k=K;
for(int i = 0;i < N-1;i++)
{
auto[x, y]=H[i];
auto w=L[i];
adj[x].pb({y, w});
adj[y].pb({x, w});
}
decompose(1);
return ans;
}
// int main()
// {
// cin.tie(0) -> sync_with_stdio(0);
// }
