#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#include <vector>
int n;
lld pref[1000000];
lld distX[1000000];
lld distY[1000000];
vector<pair<int,lld> >nei[1000000];
void DFSX(int node, lld dist=0){
distX[node]=dist;
trav(a,nei[node]){
if(distX[a.first]==-1){
DFSX(a.first,dist+a.second);
}
}
}
void DFSY(int node, lld dist=0){
distY[node]=dist;
trav(a,nei[node]){
if(distY[a.first]==-1){
DFSY(a.first,dist+a.second);
}
}
}
vector<lld> diffs;
vector<lld> dists[1000000];
vector<lld >gains[1000000];
vector<lld >gainsX[1000000];
vector<lld >gainsY[1000000];
lld absol(lld x){
return max(x,-x);
}
vector<lld> DP[1000000][3];
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
n=N;
rep(i,0,n)nei[i].clear(),distX[i]=-1,distY[i]=-1;
rep(i,0,n-1){
nei[U[i]].push_back({V[i],W[i]});
nei[V[i]].push_back({U[i],W[i]});
}
DFSX(X);
DFSY(Y);
priority_queue<lld> pq;
rep(i,0,n){
pq.push(-distX[i]);
pq.push(-distY[i]);
}
lld sum=0;
int cnt=0;
while(!pq.empty() && sum<=K){
lld d=-pq.top();
pq.pop();
sum+=d;
cnt++;
}
if(sum>K)cnt--;
int ans=cnt;
diffs.clear();
rep(i,0,n)diffs.push_back(distX[i]-distY[i]);
sort(diffs.begin(),diffs.end());
diffs.resize(unique(diffs.begin(),diffs.end())-diffs.begin());
int m=diffs.size();
rep(i,0,m)gains[i].clear(),dists[i].clear(),gainsX[i].clear(),gainsY[i].clear();
rep(i,0,n){
int pos=lower_bound(diffs.begin(),diffs.end(),distX[i]-distY[i])-diffs.begin();
dists[pos].push_back(min(distX[i],distY[i]));
}
rep(i,0,m)sort(dists[i].begin(),dists[i].end());
rep(i,0,m){
lld delta=absol(diffs[i]);
int cnt=0;
gains[i].push_back(0);
gains[i].push_back(delta);
gains[i].push_back(dists[i][0]);
rep(j,1,(int)dists[i].size()){
lld a=dists[i][j];
if(a<delta){
gains[i].push_back(a);
cnt++;
}else{
while(cnt>0){
gains[i].push_back(delta);
cnt--;
}
gains[i].push_back(a);
cnt++;
}
}
while(cnt>0){
gains[i].push_back(delta);
cnt--;
}
rep(j,0,(int)gains[i].size()-1)gains[i][j+1]+=gains[i][j];
gains[i][0]=1e18;
gains[i][1]=1e18;
gainsX[i].push_back(0);
trav(a,dists[i]){
gainsX[i].push_back(a);
}
gainsY[i].push_back(0);
trav(a,dists[i])gainsY[i].push_back(a+delta);
rep(j,0,(int)gainsX[i].size()-1)gainsX[i][j+1]+=gainsX[i][j];
rep(j,0,(int)gainsY[i].size()-1)gainsY[i][j+1]+=gainsY[i][j];
gainsX[i][0]=1e18;
gainsY[i][0]=1e18;
if(diffs[i]>0)swap(gainsX[i],gainsY[i]);
}
rep(i,0,m+1){
rep(j,0,3)DP[i][j].clear();
}
DP[0][0].resize(2*n+1,1e18);
DP[0][1].resize(2*n+1,1e18);
DP[0][2].resize(2*n+1,1e18);
DP[0][0][0]=0;
DP[0][1][0]=0;
DP[0][2][0]=0;
rep(i,0,m){
rep(j,0,3){
DP[i+1][j].resize(2*n+1,1e18);
}
rep(l,0,3){
rep(j,l,3){
rep(k,0,2*n+1){
if(j==0){
rep(o,0,(int)gainsX[i].size()){
if(o+k<=2*n)DP[i+1][j][o+k]=min(DP[i+1][j][o+k],DP[i][l][k]+gainsX[i][o]);
}
}
if(j==1){
rep(o,0,(int)gains[i].size()){
if(o+k<=2*n)DP[i+1][j][o+k]=min(DP[i+1][j][o+k],DP[i][l][k]+gains[i][o]);
}
}
if(j==2){
rep(o,0,(int)gainsY[i].size()){
if(o+k<=2*n)DP[i+1][j][o+k]=min(DP[i+1][j][o+k],DP[i][l][k]+gainsY[i][o]);
}
}
}
}
}
}
rep(i,0,2*n+1){
//cout<<DP[m][2][i]<<" ";
rep(j,0,3){
if(DP[m][j][i]<=K)ans=max(ans,i);
}
}
return ans;
}
