#include"closing.h"
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 400000
using namespace std;
const long long inf=(long long)(1e18);
struct reads
{
	int num,data;
};
int n,length,rt,fa[N+1],fa2[N+1],cl[N+1];
long long tong[N+1],dis[N+1],dis2[N+1],dp[2][N+1];
bool used[N+1];
vector<reads>E[N+1];
void add(int x,int y,int z)
{
	E[x].push_back((reads){y,z}),E[y].push_back((reads){x,z});
	return;
}
void dfs(int x)
{
	used[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i].num])
			fa[E[x][i].num]=x,dis[E[x][i].num]=dis[x]+E[x][i].data,dfs(E[x][i].num);
	return;
}
void dfs2(int x)
{
	used[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i].num])
			fa2[E[x][i].num]=x,dis2[E[x][i].num]=dis2[x]+E[x][i].data,dfs2(E[x][i].num);
	return;
}
int max_score(int SN,int X,int Y,long long K,vector<int>U,vector<int>V,vector<int>W)
{
	int op=0,x,ans=0;
	long long res=0,minn=inf;
	n=SN,length=0;
	for (int i=0;i<n;++i) E[i].clear(),used[i]=dis[i]=dis2[i]=0;
	for (int i=0;i<n;++i) add(U[i],V[i],W[i]);
	dfs(X);
	for (int i=0;i<n;++i) used[i]=0;
	dfs2(Y);
	for (int i=0;i<n;++i)
		if (max(dis[i],dis2[i])<minn)
			minn=max(dis[i],dis2[i]),rt=i;
	for (int i=0;i<n;++i) tong[++length]=min(dis[i],dis2[i]);
	sort(tong+1,tong+length+1);
	for (int i=1;i<=length;++i)
	{
		res+=tong[i];
		if (res<=K) ans=max(ans,i);
	}
	x=rt,cl[x]=2;
	while (x!=X) x=fa[x],cl[x]=1;
	x=rt;
	while (x!=Y) x=fa2[x],cl[x]=1;
	for (int i=0;i<=(n<<1);++i) dp[0][i]=inf;
	dp[0][0]=0;
	for (int i=0;i<n;++i)
	{
		op^=1;
		for (int j=0;j<=(n<<1);++j) dp[op][j]=inf;
		for (int j=(n<<1);j>=0;--j)
		{
			if (!cl[i]) dp[op][j]=min(dp[op][j],dp[op^1][j]);
			if (cl[i]!=2&&j) dp[op][j]=min(dp[op][j],dp[op^1][j-1]+min(dis[i],dis2[i]));
			if (j>=2) dp[op][j]=min(dp[op][j],dp[op^1][j-2]+max(dis[i],dis2[i]));
		}
	}
	for (int i=0;i<=(n<<1);++i)
		if (dp[op][i]<=K)
			ans=max(ans,i);
    return ans;
}