#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 100007
using namespace std;
int n,m,maxx;
vector<long long> dp[MAXN][2];
vector<bool> li[MAXN][2];
vector< pair<int,int> > good[MAXN],s[MAXN];
long long sum(int pos,int l,int r){
int res=0;
for(int i=0;i<s[pos].size();i++){
if(s[pos][i].first>=l and s[pos][i].first<=r)res+=s[pos][i].second;
}
return res;
}
long long ff(int pos,int last,int flag){
if(pos==-1)return 0;
if(li[pos][flag][last])return dp[pos][flag][last];
li[pos][flag][last]=true;
for(int i=0;i<good[pos].size() and good[pos][i].first<=good[pos+1][last].first;i++){
dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,1)+sum(pos,good[pos][i].first,good[pos+1][last].first));
dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,0));
}
for(int i=good[pos].size()-1;i>=0 and good[pos][i].first>good[pos+1][last].first;i--){
if(flag==0)dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,0)+sum(pos+1,good[pos+1][last].first,good[pos][i].first));
else dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,0));
}
return dp[pos][flag][last];
}
long long max_weights(int N, int M,vector<int> X,vector<int> Y,vector<int> W){
n=N; m=M;
for(int i=0;i<m;i++){
s[X[i]].push_back({Y[i]+1,W[i]});
good[X[i]-1].push_back({Y[i]+1,W[i]});
good[X[i]+1].push_back({Y[i]+1,W[i]});
}
for(int i=0;i<=n;i++){
good[i].push_back({0,0});
sort(good[i].begin(),good[i].end());
sort(s[i].begin(),s[i].end());
dp[i][0].resize(good[i+1].size()+5);
dp[i][1].resize(good[i+1].size()+5);
li[i][0].resize(good[i+1].size()+5);
li[i][1].resize(good[i+1].size()+5);
}
return ff(n-1,0,0);
}
/*
int main(){
cout<<max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3})<<"\n";
}
*/
