long long max_weights(int N,int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W){
	std::map<int,int> mp;
	std::vector<int> v;
	int cur=0;
	for(int i:X)v.push_back(i);
	for(int i:Y)v.push_back(i);
	for(int i=0;i<N;i++)v.push_back(i);
	std::sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	std::vector<std::vector<long long>> dp[4];
	std::vector<std::vector<long long>> pref;
	for(int i=0;i<4;i++){
		dp[i].resize((int)v.size()+5);
	}
	for(int i:v)mp[i]=cur++;
	std::vector<int> g[(int)v.size()+5];
	std::map<std::pair<int,int>,int> mpp;
	for(int i=0;i<M;i++){
		g[mp[X[i]]].push_back(mp[Y[i]]);
		mpp[{mp[X[i]],mp[Y[i]]}]=W[i];
	}
	int sz=(int)v.size();
	for(int i=0;i<sz;i++){
		g[i].push_back(-1);
		std::sort(g[i].begin(),g[i].end());
		pref.push_back(std::vector<long long>());
		pref[i].push_back(0);
		for(int j=1;j<(int)g[i].size();j++){
			pref[i].push_back(pref[i].back()+mpp[{i,g[i][j]}]);
		}
	}
	for(int i=0;i<(int)g[0].size();i++){
		dp[0][0].push_back(0);
		dp[1][0].push_back(-pref[0][i]);
		dp[2][0].push_back(0);
		dp[3][0].push_back(0);
		int lo=0,hi=(int)g[1].size()-1;
		for(;lo<=hi;){
			int mi=(lo+hi)>>1;
			if(g[1][mi]<=g[0][i]){
				lo=mi+1;
				dp[2][0][i]=pref[1][mi];
			}else{
				hi=mi-1;
			}
		}
	}
	for(int i=1;i<N;i++){
		int k=0;
		for(int j=0;j<(int)g[i].size();j++){
			dp[0][i].push_back(0);
			long long mx=0;
			for(;k<(int)g[i-1].size()&&g[i-1][k]<=g[i][j];){
				mx=std::max(mx,dp[1][i-1][k]);
				k++;
			}
			dp[0][i][j]=std::max(dp[0][i][j],pref[i-1][k-1]+mx);
			dp[1][i].push_back(dp[0][i][j]-pref[i][j]);
		}
		k=(int)g[i-1].size()-1;
		for(int j=(int)g[i].size()-1;j>=0;j--){
			dp[3][i].push_back(0);
			long long mx=0;
			for(;k>=0&&g[i-1][k]>=g[i][j];){
				mx=std::max(mx,dp[2][i-1][k]);
				k--;
			}
			dp[3][i][(int)g[i].size()-1-j]=std::max(dp[3][i][(int)g[i].size()-1-j],-pref[i][j]+mx);
			if(!i)dp[0][i][(int)g[i].size()-1-j]=std::max(dp[0][i][(int)g[i].size()-1-j],dp[3][i][(int)g[i].size()-1-j]-pref[i][j]);
			long long nxt=std::max(dp[3][i][(int)g[i].size()-1-j],dp[0][i][(int)g[i].size()-1-j]);
			if(i!=N-1){
				int tot=0;
				int lo=0,hi=(int)g[i+1].size()-1;
				for(;lo<=hi;){
					int mi=(lo+hi)>>1;
					if(g[i+1][mi]<=g[i][j]){
						lo=mi+1;
						tot=pref[i+1][mi];
					}else{
						hi=mi-1;
					}
				}
				dp[2][i].push_back(nxt+tot);
			}
		}
	}
	long long ans=0;
	for(int i=0;i<sz;i++){
		for(int j=0;j<(int)g[i].size();j++){
			long long res=dp[0][i][j];
			ans=std::max(ans,res);
		}
	}
	return ans;
}

long long max_weights(int N,int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W){
	long long dp[N+5][N+5][2];
	for(int i=0;i<=N;i++){
		for(int j=0;j<=N;j++){
			for(int k=0;k<2;k++){
				dp[i][j][k]=0;
			}
		}
	}
	int A[N+5][N+5];
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			A[i][j]=0;
		}
	}
	for(int i=0;i<M;i++){
		A[Y[i]][X[i]]=W[i];
	}
	for(int j=1;j<N;j++){
		for(int i=0;i<=N;i++){
			long long sum=0;
			dp[i][j][1]=std::max(dp[i][j][1],dp[i][j-1][1]);
			for(int k=i;k<N;k++){
				sum+=A[k][j-1];
				dp[k+1][j][1]=std::max(dp[k+1][j][1],dp[i][j-1][1]+sum);
			}
		}
		for(int i=0;i<=N;i++){
			long long sum=0;
			for(int k=i;k>=0;k--){
				if(k<i)sum+=A[k][j];
				dp[k][j][0]=std::max(dp[k][j][0],dp[i][j-1][0]+sum);
				dp[k][j][0]=std::max(dp[k][j][0],dp[i][j-1][1]+sum);
				if(!k)dp[k][j][1]=std::max(dp[k][j][1],dp[k][j][0]-sum);
			}
		}
	}
	long long ans=0;
	for(int i=0;i<N;i++){
		long long sum=0;
		for(int j=0;j<=N;j++){
			ans=std::max(ans,std::max(dp[j][i][0]+sum,dp[j][i][1]+sum));
			if(i<N-1)sum+=A[j][i+1];
		}
	}
	return ans;
}