#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
using ll = long long;
const ll inf = 1e18;
vector<vector<pair<int, int>>> adj;
vector<vector<ll>> dist;
void init( int n ){
adj.clear(); adj.resize(n);
dist.clear(); dist.resize( 2, vector<ll>(n));
}
void dfs( int cur, int pai, int t ){
for( auto [viz, d] : adj[cur] ) if( viz != pai ){
dist[t][viz] = dist[t][cur] + d;
dfs( viz, cur, t );
}
}
int max_score(int n, int x, int y, long long k, vector<int> a, vector<int> b, vector<int> c ) {
init(n);
int m = a.size();
for( int i = 0; i < m; i++ ){
adj[a[i]].push_back({ b[i], c[i] });
adj[b[i]].push_back({ a[i], c[i] });
}
dfs( x, x, 0 );
dfs( y, y, 1 );
tuple<ll, ll, ll> opt( inf, inf, inf );
for( int i = 0; i < n; i++ ) opt = min( opt, make_tuple( abs(dist[0][i] - dist[1][i]), dist[0][i] + dist[1][i], (ll)i ) );
int z = get<2>(opt);
vector<int> marc(n);
set<pair<ll, int>> s;
s.insert({ 0, x });
s.insert({ 0, y });
marc[x] = marc[y] = true;
int resp = 0;
while( !s.empty() ){
auto [cost, cur] = *s.begin(); s.erase(s.begin());
if( cost > k ) break;
k -= cost;
resp++;
marc[cur] = true;
for( auto [viz, d] : adj[cur] ) if( !marc[viz] ) s.insert({ cost + d, viz });
}
return resp;
}
