//ANMHLIJKTJIY!
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include "closing.h"
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 200010
#define M 550010
using namespace std;
ll nxtx[3][3]={{0,-1,-1},{1,-1,-1},{1,1,2}},nxty[3][3]={{0,1,1},{0,-1,1},{-1,-1,2}};
ll n,sx,sy,lim,dis[N][2],fa[N],bel[N],mn[M][3][3][2];
bool vis[N];
vector<pair<ll,ll> > vt[N];
vector<ll> nds[N],seq,dp[M][3][3][2];
void predfs(ll x,ll lst,ll id,ll d)
{
	ll i;
	dis[x][id]=d;
	fa[x]=lst;
	for(i=0;i<vt[x].size();i++)
	{
		if(vt[x][i].F!=lst)
		{
			predfs(vt[x][i].F,x,id,d+vt[x][i].S);
		}
	}
	return;
}
void dfsbel(ll x,ll lst,ll tp)
{
	if(vis[x])
	{
		tp=x;
	}
	bel[x]=tp;
	nds[tp].push_back(x);
	ll i;
	for(i=0;i<vt[x].size();i++)
	{
		if(vt[x][i].F!=lst)
		{
			dfsbel(vt[x][i].F,x,tp);
		}
	}
	return;
}
void Merge(ll p,ll p0,ll p1,ll p2,ll u,ll u0,ll u1,ll u2,ll v,ll v0,ll v1,ll v2)
{
	ll i,j,lo=(mn[u][u0][u1][u2]+mn[v][v0][v1][v2]-mn[p][p0][p1][p2])/2;
	for(i=0;i<dp[u][u0][u1][u2].size();i++)
	{
		for(j=0;j<dp[v][v0][v1][v2].size();j++)
		{
			while(dp[p][p0][p1][p2].size()<=lo+i+j)
			{
				dp[p][p0][p1][p2].push_back(LINF);
			}
			dp[p][p0][p1][p2][lo+i+j]=min(dp[p][p0][p1][p2][lo+i+j],dp[u][u0][u1][u2][i]+dp[v][v0][v1][v2][j]);
		}
	}
	return;
}
void solve(ll x,ll l,ll r)
{
	ll i,j,k,d,p,q;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			for(k=0;k<2;k++)
			{
				dp[x][i][j][k].clear();
				mn[x][i][j][k]=INF;
			}
		}
	}
	if(l==r)
	{
		ll u=seq[l];
		dp[x][0][0][0].push_back(0);
		mn[x][0][0][0]=0;
		vector<ll> allv;
		for(i=0;i<nds[u].size();i++)
		{
			allv.push_back(dis[nds[u][i]][0]);
		}
		sort(allv.begin(),allv.end());
		mn[x][2][0][0]=2;
		mn[x][2][0][1]=1;
		ll v=0;
		for(i=0;i<allv.size();i++)
		{
			v+=allv[i];
			if(i&1)
			{
				dp[x][2][0][0].push_back(v);
			}
			else
			{
				dp[x][2][0][1].push_back(v);
			}
		}
		for(i=0;i<nds[u].size();i++)
		{
			allv[i]=dis[nds[u][i]][1];
		}
		sort(allv.begin(),allv.end());
		mn[x][0][2][0]=2;
		mn[x][0][2][1]=1;
		v=0;
		for(i=0;i<allv.size();i++)
		{
			v+=allv[i];
			if(i&1)
			{
				dp[x][0][2][0].push_back(v);
			}
			else
			{
				dp[x][0][2][1].push_back(v);
			}
		}
		ll delta=abs(dis[u][0]-dis[u][1]);
		for(i=0;i<nds[u].size();i++)
		{
			allv[i]=min(dis[nds[u][i]][0],dis[nds[u][i]][1]);
		}
		sort(allv.begin(),allv.end());
		mn[x][2][2][0]=2;
		mn[x][2][2][1]=3;
		dp[x][2][2][0].push_back(v=allv[0]+delta);
		for(i=1;i<allv.size()&&allv[i]<delta;i++)
		{
			v+=allv[i];
			dp[x][2][2][i&1].push_back(v);
		}
		for(j=1;j<i;j++)
		{
			v+=delta;
			dp[x][2][2][(i+j)&1].push_back(v);
		}
		for(;i<allv.size();i++)
		{
			v+=allv[i];
			dp[x][2][2][1].push_back(v);
			v+=delta;
			dp[x][2][2][0].push_back(v);
		}
//		cout<<l<<"~"<<r<<":\n";
//		for(i=0;i<3;i++)
//		{
//			for(j=0;j<3;j++)
//			{
//				for(k=0;k<2;k++)
//				{
//					cout<<i<<","<<j<<","<<k<<": "<<mn[x][i][j][k]<<": ";
//					for(d=0;d<dp[x][i][j][k].size();d++)
//					{
//						cout<<dp[x][i][j][k][d]<<" , ";
//					}
//					puts("");
//				}
//			}
//		}
		return;
	}
	ll mid=(l+r)>>1,a=x<<1;
	solve(a,l,mid);
	solve(a|1,mid+1,r);
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			for(k=0;k<2;k++)
			{
				for(d=0;d<3;d++)
				{
					for(p=0;p<3;p++)
					{
						if(nxtx[i][d]==-1||nxty[j][p]==-1)
						{
							continue;
						}
						for(q=0;q<2;q++)
						{
							mn[x][nxtx[i][d]][nxty[j][p]][k^q]=min(mn[x][nxtx[i][d]][nxty[j][p]][k^q],mn[a][i][j][k]+mn[a|1][d][p][q]);
						}
					}
				}
			}
		}
	}
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			for(k=0;k<2;k++)
			{
				for(d=0;d<3;d++)
				{
					for(p=0;p<3;p++)
					{
						if(nxtx[i][d]==-1||nxty[j][p]==-1)
						{
							continue;
						}
						for(q=0;q<2;q++)
						{
							Merge(x,nxtx[i][d],nxty[j][p],k^q,a,i,j,k,a|1,d,p,q);
						}
					}
				}
			}
		}
	}
//	cout<<l<<"~"<<r<<":\n";
//	for(i=0;i<3;i++)
//	{
//		for(j=0;j<3;j++)
//		{
//			for(k=0;k<2;k++)
//			{
//				cout<<i<<","<<j<<","<<k<<": "<<mn[x][i][j][k]<<": ";
//				for(d=0;d<dp[x][i][j][k].size();d++)
//				{
//					cout<<dp[x][i][j][k][d]<<" , ";
//				}
//				puts("");
//			}
//		}
//	}
	return;
}
int max_score(int _n,int _x,int _y,ll _k,vector<int> U,vector<int> V,vector<int> W)
{
	ll i,j,k;
	n=_n;
	sx=_x,sy=_y,lim=_k;
	for(i=0;i<n;i++)
	{
		nds[i].clear();
		vis[i]=false;
		vt[i].clear();
	}
	for(i=0;i<U.size();i++)
	{
		vt[U[i]].push_back(make_pair(V[i],W[i]));
		vt[V[i]].push_back(make_pair(U[i],W[i]));
	}
	predfs(sx,-1,0,0);
	predfs(sy,-1,1,0);
	seq.clear();
	for(i=sx;i>=0;i=fa[i])
	{
		seq.push_back(i);
		vis[i]=true;
	}
	dfsbel(sx,-1,sx);
	solve(1,0,seq.size()-1);
	ll ret=0;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			for(k=0;k<2;k++)
			{
				ll p=lower_bound(dp[1][i][j][k].begin(),dp[1][i][j][k].end(),lim+1)-dp[1][i][j][k].begin()-1;
				if(p>=0)
				{
					ret=max(ret,p*2+mn[1][i][j][k]);
				}
			}
		}
	}
	return ret;
}