#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
vector<vector<pair<int, int>>> graph(N);
for (int i = 0; i < (int)U.size(); ++i) {
graph[U[i]].emplace_back(V[i], W[i]);
graph[V[i]].emplace_back(U[i], W[i]);
}
auto precomp = [&](int src) {
vector<int> q = {src};
vector<long long> ret(N, -1);
ret[src] = 0;
for (int i = 0; i < N; ++i) {
int node = q[i];
for (auto [vec, cost] : graph[node]) {
if (ret[vec] == -1) {
ret[vec] = ret[node] + cost;
q.push_back(vec);
}
}
}
return ret;
};
vector<int> xy = {X, Y};
vector<vector<long long>> dist = {precomp(X), precomp(Y)};
vector<vector<int>> taken = {vector<int>(N, 0), vector<int>(N, 0)};
priority_queue<tuple<long long, int, int>> pq;
auto push = [&](int z, int node) {
long long d = dist[z][node];
if (taken[z][node]) return;
pq.emplace(-d, z, node);
};
push(0, xy[0]); push(1, xy[1]);
int ans = 0;
while (pq.size()) {
auto [_, z, node] = pq.top(); pq.pop();
long long d = dist[z][node];
if (taken[!z][node]) d = max(0LL, d - dist[!z][node]);
if (d > K) break;
K -= d; ++ans;
taken[z][node] = true;
for (auto [vec, _] : graph[node])
push(z, vec);
}
return ans;
}
