#include"fish.h"
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define N 3005

inline void chk(ll &x,ll y){
	x=std::max(x,y);
}

std::map<std::pair<int,int>,int> mp;
std::vector<int> V[N];
std::vector<ll> S[N];

inline ll s(int i,int j){
	int o=std::upper_bound(V[i].begin(),V[i].end(),j)-V[i].begin()-1;
	return o>=0?S[i][o]:0;
}

ll f[N],g[N],F[N],G[N];

ll max_weights(int n,int m,std::vector<int> a,std::vector<int> b,std::vector<int> c){
	for(int i=0;i<m;i++)
		V[a[i]+1].emplace_back(b[i]),mp[{a[i]+1,b[i]+1}]=c[i];
	for(int i=1;i<=n;i++){
		V[i].emplace_back(n),std::sort(V[i].begin(),V[i].end());
		S[i].resize(V[i].size());
		for(int j=0;j<(int)V[i].size()-1;j++)
			S[i][j+1]=mp[{i,V[i][j]+1}];
		for(int j=1;j<(int)V[i].size();j++)
			S[i][j]+=S[i][j-1];
	}
	V[0].emplace_back(0),S[0].emplace_back(0);
	memset(f,~0x3f,sizeof(f)),memset(g,~0x3f,sizeof(g));
	f[0]=g[0]=0;
	for(int i=1;i<=n;i++){
		for(auto x:V[i-1]){
			chk(F[*std::lower_bound(V[i].begin(),V[i].end(),x)],g[x]+s(i,x));
			for(auto y:V[i]){
				if(x>=y){
					chk(F[y],f[x]),chk(G[y],f[x]);
					chk(G[y],g[x]+s(i,x)-s(i,y));
				}
				else{
					chk(F[y],f[x]+s(i-1,y)-s(i-1,x)),chk(G[y],f[x]+s(i-1,y)-s(i-1,x));
					chk(F[y],g[x]),chk(G[y],g[x]);
				}
			}
		}
		for(auto y:V[i])
			f[y]=F[y],g[y]=G[y],F[y]=G[y]=~inf;
	}
	ll res=0;
	for(auto i:V[n])
		chk(res,f[i]),chk(res,g[i]);
	return res;
}