#include "closing.h"

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    using data = tuple<ll, int, int, int>;
    priority_queue<data, vector<data>, greater<data>> pq;
    vector<ll> dx(N, 0), dy(N, 0);

    vector adj(N, vector<pair<int,int>>());
    for(int i = 0; i < U.size(); ++i) {
        adj[U[i]].emplace_back(V[i], W[i]);
        adj[V[i]].emplace_back(U[i], W[i]);
    }

    const auto dfs = [&](const auto &self, vector<ll> &d, int node, int from) -> void {
        for(auto &[next, c] : adj[node]) {
            if(next == from) continue;
            d[next] = d[node] + c;
            self(self, d, next, node);
        }
    };
    dfs(dfs, dx, X, -1);
    dfs(dfs, dy, Y, -1);

    vector<bool> vx(N, false), vy(N, false);
    int ans = 2;

    vx[X] = vy[Y] = true;
    for(auto &[next, _] : adj[X]) {
        int mask = (vx[next] ? 1 : 0) + (vy[next] ? 2 : 0);
        pq.emplace(dx[next], next, mask, 1);
    }
    for(auto &[next, _] : adj[Y]) {
        int mask = (vx[next] ? 1 : 0) + (vy[next] ? 2 : 0);
        pq.emplace(dy[next], next, mask, 2);
    }

    ll tot = 0;
    for(; !pq.empty(); ) {
        auto [cost, cur, state, app] = pq.top();
        pq.pop();

        if(app == 1 && vx[cur]) continue;
        if(app == 2 && vy[cur]) continue;

        int mask = (vx[cur] ? 1 : 0) + (vy[cur] ? 2 : 0);
        if(mask != state) continue;

        if(tot + cost > K) break;
        tot += cost;
        ++ans;

        if(app == 1) {
            vx[cur] = true;
            mask = (vx[cur] ? 1 : 0) + (vy[cur] ? 2 : 0);
            if(!vy[cur]) {
                bool can = false;
                for(auto &[next, _] : adj[cur]) {
                    can |= vy[next];
                }
                if(can) pq.emplace(max(0LL, dy[cur] - dx[cur]), cur, mask, 2);
            }

            for(auto &[next, _] : adj[cur]) {
                if(vx[next]) continue;
                ll nxt = (vy[next] ? max(0LL, dx[next] - dy[next]) : dx[next]);
                int msk = (vy[next] ? 2 : 0);
                pq.emplace(nxt, next, msk, 1);
            }
        }
        else {
            vy[cur] = true;
            mask = (vx[cur] ? 1 : 0) + (vy[cur] ? 2 : 0);
            if(!vx[cur]) {
                bool can = false;
                for(auto &[next, _] : adj[cur]) {
                    can |= vx[next];
                }
                if(can) pq.emplace(max(0LL, dx[cur] - dy[cur]), cur, mask, 1);
            }

            for(auto &[next, _] : adj[cur]) {
                if(vy[next]) continue;
                ll nxt = (vx[next] ? max(0LL, dy[next] - dx[next]) : dy[next]);
                int msk = (vx[next] ? 1 : 0);
                pq.emplace(nxt, next, msk, 2);
            }
        }
    }

    return ans;
}