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

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::lower_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]=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));
		ll A=~inf,B=~inf;
		for(int j=(int)V[i-1].size()-1,k=(int)V[i].size()-1;j>=0||k>=0;){
			if(j>=0&&(k<0||V[i-1][j]>V[i][k])){
				int x=V[i-1][j--];
				chk(A,f[x]),chk(B,g[x]+s(i,x));
			}
			else{
				int y=V[i][k--];
				chk(F[y],A),chk(G[y],A),chk(G[y],B-s(i,y));
			}
		}
		A=B=~inf;
		for(int j=0,k=0;j<(int)V[i-1].size()||k<(int)V[i].size();){
			if(j<(int)V[i-1].size()&&(k>=(int)V[i].size()||V[i-1][j]<V[i][k])){
				int x=V[i-1][j++];
				chk(A,f[x]-s(i-1,x)),chk(B,g[x]);
			}
			else{
				int y=V[i][k++];
				chk(F[y],A+s(i-1,y)),chk(G[y],A+s(i-1,y)),chk(F[y],B),chk(G[y],B);
			}
		}
		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;
}