#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int>> G[201000];
int Vis[201000] /*0 - N, 1 - X, 2 - Y, 3 - X e Y*/, Vxy[10] /*1 - X 2 - Y*/, Pes[201000];
priority_queue<pair<int,pair<int,pair<int,int>>>> Q; // valor, atual, pai, base X=1 Y=2
int32_t max_score(int32_t N, int32_t X, int32_t Y, int K, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
for (int i = 0; i < N-1; i++) {
G[U[i]].push_back(make_pair(V[i],W[i]));
G[V[i]].push_back(make_pair(U[i],W[i]));
Vis[i] = 0;
Pes[i] = 0;
}
Pes[N-1] = 0;
Vis[N-1] = 0;
Q.push(make_pair(0, make_pair(X,make_pair(X,1))));
Q.push(make_pair(0, make_pair(Y,make_pair(Y,2))));
int S = 0;
int R = 0;
while (Q.empty() == false and S<K) {
pair<int,pair<int,pair<int,int>>> Atual = Q.top();
Q.pop();
if (Vis[Atual.second.first]&Atual.second.second.second) continue;
if (S+Atual.first > K) break;
if (Atual.second.first == X and Atual.second.second.second==2) Vxy[1] = Atual.first;
if (Atual.second.first == Y and Atual.second.second.second==1) Vxy[2] = Atual.first;
S += Atual.first;
R++;
Pes[Atual.second.first] = Atual.first;
int Lp = 0;
for (int i = 0; i < G[Atual.second.first].size(); i++) {
if (G[Atual.second.first][i].first == Atual.second.second.first) Lp = G[Atual.second.first][i].second;
if (Vis[Atual.second.first] == 0) {
if (Vis[G[Atual.second.first][i].first] == 0) Q.push(make_pair(Atual.first+G[Atual.second.first][i].second,make_pair(G[Atual.second.first][i].first,make_pair(Atual.second.first,Atual.second.second.second))));
else if (Vis[G[Atual.second.first][i].first]&Atual.second.second.second == 0) {
Q.push(make_pair(((Atual.first+G[Atual.second.first][i].second>Pes[G[Atual.second.first][i].first])?Atual.first+G[Atual.second.first][i].second-Pes[G[Atual.second.first][i].first]:0),make_pair(G[Atual.second.first][i].first,make_pair(Atual.second.first,Atual.second.second.second))));
}
} else {
if (Vis[G[Atual.second.first][i].first]&Atual.second.second.second == 0) {
Q.push(make_pair(((Atual.first+G[Atual.second.first][i].second>Pes[G[Atual.second.first][i].first])?Atual.first+G[Atual.second.first][i].second-Pes[G[Atual.second.first][i].first]:0),make_pair(G[Atual.second.first][i].first,make_pair(Atual.second.first,Atual.second.second.second))));
}
}
}
if (Vis[Atual.second.first] == 0 && Vis[Atual.second.second.first] != Atual.second.second.second) Q.push(make_pair((Lp+Pes[Atual.second.second.first]>Atual.first)?Lp+Pes[Atual.second.second.first]-Atual.first:0,make_pair(Atual.second.first,make_pair(Atual.second.second.first,3-Atual.second.second.second))));
Vis[Atual.second.first] += Atual.second.second.second;
}
while (Q.empty()==false) Q.pop();
for (int i = 0; i < N; i++) while (G[i].empty()==false) G[i].pop_back();
return R;
}
