#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using ar = array<ll,2>;
using vi = vector<ll>;
const int mxN = (int)3e5+10;
const ll LINF = (ll)2e18;
ar a[mxN];
ll n, dis[2][mxN], dp[3010][6010];
vector<pair<int,ll>> adj[mxN];
void dfs(int s, int p, int t){
for(auto [u,w] : adj[s]){
if(u==p) continue;
dis[t][u] = dis[t][s]+w; dfs(u,s,t);
}
}
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
n = N; int ans = 0;
for(int i = 0; i <= n; i++) adj[i].clear();
for(int i = 0; i < sz(U); i++){
auto [a,b,c] = tie(U[i],V[i],W[i]);
adj[a].pb({b,c}), adj[b].pb({a,c});
}
dis[0][X]=dis[1][Y]=0;
dfs(X,-1,0); dfs(Y,-1,1);
vi v; v.clear();
for(int i = 0; i < n; i++){
ll mn = min(dis[0][i],dis[1][i]);
ll mx = max(dis[0][i],dis[1][i]);
a[i][0] = mn, a[i][1] = mx;
v.pb(mn), v.pb(mx);
}
ll D = 0; int i = 0; sort(all(v));
for(auto u : v){
D+=u; if(D<=K) ans=i+1;
i++;
}
if(n>3000) return ans;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= 2*n+4; j++)
dp[i][j] = LINF;
dp[0][0] = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j <= 2*i; j++){
if(dis[0][i]+dis[1][i]!=dis[0][Y])
dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
for(int k : {0,1})
dp[i+1][j+k+1] = min(dp[i+1][j+k+1], dp[i][j]+a[i][k]);
}
}
for(int i = 0; i <= 2*n; i++)
if(dp[n][i]<=K) ans=max(ans,i);
return ans;
}
