#include "closing.h"
#include <bits/stdc++.h>
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 ((ll) 1 << 30)
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
using namespace std;
vector<vector<pair<ll, ll>>> adj;
vector<ll> memo;
struct TPos {
ll i, wth = -INF64, from;
bool from_x;
string toString() {
return to_string(i) + ":" + to_string(wth) + ":" + to_string(from);
}
};
bool operator < (const TPos& a, const TPos& b) {
return (a.wth - memo[a.i] > b.wth - memo[b.i]);
}
struct Fut {
TPos px, py;
};
vector<Fut> fut;
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
adj.clear();
adj.resize(N);
memo.clear();
memo.resize(N);
fut.clear();
fut.resize(N);
range(i, 0, N - 1){
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
pqueue<TPos> pq;
pq.push({X, 0, X, 1});
fut[X].px = {X, 0, X, 1};
pq.push({Y, 0, Y, 0});
fut[Y].py = {Y, 0, Y, 0};
ll ans = 0;
ll sum = 0;
TPos t;
while (!pq.empty()) {
t = pq.top(); pq.pop();
if (t.from_x && fut[t.i].px.wth == -INF64) continue;
if (!t.from_x && fut[t.i].py.wth == -INF64) continue;
ll dif = t.wth - memo[t.i];
if (sum + dif > K) break;
ans++;
sum += dif;
memo[t.i] = t.wth;
if (t.from_x) {
fut[t.i].px.wth = -INF64;
if (fut[t.i].py.wth != -INF64)
pq.push({fut[t.i].py});
}
else {
fut[t.i].py.wth = -INF64;
if (fut[t.i].px.wth != -INF64)
pq.push({fut[t.i].px});
}
for (pair<ll, ll> k : adj[t.i]) {
if (k.first != t.from) {
TPos nt = {k.first, t.wth + k.second, t.i, t.from_x};
pq.push(nt);
if (t.from_x) fut[nt.i].px = nt;
else fut[nt.i].py = nt;
}
}
}
return ans;
}
