#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define ull unsigned long long 
#define sz(a) ((int) a.size())
#define vi vector<int>
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1 << 21, L = 5e5, mod = 998244353;
vector < pair < int, int > > e[N];
int n;
vector < ll > bfs(int x) {
	vector < ll > dis(n);
	L(i, 0, n - 1) {
		dis[i] = 2e18;
	}
	dis[x] = 0;
	queue < int > q;
	q.push(x);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(auto&v : e[u]) {
			if(dis[v.first] > dis[u] + v.second) {
				dis[v.first] = dis[u] + v.second;
				q.push(v.first);
			}
		}
	}
	return dis;
}
int max_score(int N, int X, int Y, ll K, vi U, vi V, vi W) {
	n = N;
	L(i, 0, N - 2) {
		e[U[i]].emplace_back(V[i], W[i]);
		e[V[i]].emplace_back(U[i], W[i]);
	} 
	auto dis1 = bfs(X);
	auto dis2 = bfs(Y);
	vector < ll > dp(2 * N + 1);
	L(i, 0, 2 * N) 
		dp[i] = 2e18;
	dp[0] = 0;
	L(i, 0, n - 1) 
		if(dis1[i] > dis2[i]) 
			swap(dis1[i], dis2[i]);
	L(i, 0, N - 1) {
		R(j, i * 2, 0) {
			dp[j + 2] = min(dp[j + 2], dp[j] + dis2[i]);
			dp[j + 1] = min(dp[j + 1], dp[j] + dis1[i]);
		}
	}
	int pos = 0;
	while(pos < 2 * N && dp[pos + 1] <= K) ++pos;
	return pos;
}

//int main() {
//	cout << max_score(7, 0, 2, 10,
// vi{0, 0, 1, 2, 2, 5}, vi{1, 3, 2, 4, 5, 6}, vi{2, 3, 4, 2, 5, 3}) << '\n';
//}