#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back
void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}
template<typename T,typename V>
void PRINT(pair<T,V>& x){
cerr<<"{";
PRINT(x.fi);
cerr<<",";
PRINT(x.se);
cerr<<"}";
}
template<typename T>
void PRINT(T &x){
int id=0;
cerr<<"{";
for(auto _i:x){
cerr<<(id++ ? "," : "");
PRINT(_i);
}
cerr<<"}";
}
void _PRINT(){
cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
PRINT(h);
if(sizeof...(t)) cerr<<", ";
_PRINT(t...);
}
#define Debug(x...) { cerr<<"["<<#x<<"]=["; _PRINT(x); }
const int mxM=3e5+1;
const int mxN=1e5+1;
vector<int> inds[mxN];
map<int,ll> dp[3][mxN],val[mxN];
//map<int,ll,greater<int>> pref[mxN];
deque<pair<int,ll>> pref[mxN];
void CalcPref(int x){
for(auto p:val[x]){
int y=p.fi;
ll w=p.se;
ll ps=w+(!pref[x].empty() ? (*pref[x].begin()).se : 0LL);
pref[x].push_front({y,ps});
//pref[x][y]=w+(!pref[x].empty() ? (*pref[x].begin()).se : 0LL);
}
}
ll Sum(int x,int y1,int y2){
if(y1>y2) return 0;
else{
auto lb2=lower_bound(all(pref[x]),make_pair(y2,LINF),greater<pair<int,ll>>());
auto lb1=lower_bound(all(pref[x]),make_pair(y1-1,LINF),greater<pair<int,ll>>());
auto e=pref[x].end();
ll r=(lb2!=e ? (*lb2).se : 0);
ll l=(lb1!=e ? (*lb1).se : 0);
return r-l;
}
}
ll MaxDP(int x,int p,vector<int> v){
if(!dp[0][x].count(p)) return 0;
ll ret=-LINF;
for(int d:v) ret=max(ret,dp[d][x][p]);
return ret;
}
void MaxSelf(ll& x,ll y){
x=max(x,y);
}
long long max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W){
for(int i=0;i<M;i++){
val[X[i]][Y[i]]=W[i];
if(X[i]-1>=0) inds[X[i]-1].pb(Y[i]+1);
if(X[i]+1<N) inds[X[i]+1].pb(Y[i]+1);
}
for(int x=0;x<N;x++){
inds[x].pb(0); inds[x].pb(N);
sort(all(inds[x]));
inds[x].resize(distance(inds[x].begin(),unique(all(inds[x]))));
}
for(int x=0;x<N;x++){
CalcPref(x);
if(x==0){
for(int p:inds[x]){
for(int d=0;d<3;d++){
dp[d][x][p]=0;
}
}
}
else{
//0:Trazimo dp gde je pile na x-1 manji nego pile na x
int i1=0,i2=0;
int p1=0,p2=0;
ll mx=-LINF;
while(i2<sz(inds[x])){
while(i1<sz(inds[x-1]) && p1<p2){
ll tmp=MaxDP(x-1,p1,{1,0})+Sum(x-1,p1,p2-1);
MaxSelf(mx,tmp);
i1++;
if(i1<sz(inds[x-1])) p1=inds[x-1][i1];
}
MaxSelf(dp[0][x][p2],mx);
if(i2<sz(inds[x])-1){
int np2=inds[x][i2+1];
mx+=Sum(x-1,p2,np2-1);
}
i2++;
if(i2<sz(inds[x])) p2=inds[x][i2];
}
//1:Trazimo dp gde je pile na x-1 jednak sa pile na x
for(int p:inds[x]){
MaxSelf(dp[1][x][p],MaxDP(x-1,p,{0,1,2}));
}
//2:Trazimo dp gde je pile na x-1 veci nego pile na x
i1=sz(inds[x-1])-1,i2=sz(inds[x])-1;
p1=N,p2=N;
mx=-LINF;
while(i2>=0){
while(i1>=0 && p1>p2){
ll tmp=MaxDP(x-1,p1,{1,2})+Sum(x,p2,p1-1);
MaxSelf(mx,tmp);
i1--;
if(i1>=0) p1=inds[x-1][i1];
}
MaxSelf(dp[2][x][p2],mx);
if(i2>0 && mx!=0){
int np2=inds[x][i2-1];
mx+=Sum(x,np2,p2-1);
}
i2--;
if(i2>=0) p2=inds[x][i2];
}
if(x>1){
//Trazimo dp gde je pile na x-1 jednak 0 i na x-1 je dolina
i1=sz(inds[x-2])-1,i2=sz(inds[x])-1;
p1=N,p2=N;
mx=-LINF;
while(i2>=0){
while(i1>=0 && p1>=p2){
ll tmp=MaxDP(x-2,p1,{0,1,2})+Sum(x-1,0,p1-1);
MaxSelf(mx,tmp);
i1--;
if(i1>=0) p1=inds[x-2][i1];
}
MaxSelf(dp[0][x][p2],mx);
i2--;
if(i2>=0) p2=inds[x][i2];
}
i1=0,i2=0;
p1=0,p2=0;
mx=-LINF;
while(i2<sz(inds[x])){
while(i1<sz(inds[x-2]) && p1<p2){
ll tmp=MaxDP(x-2,p1,{0,1,2})+Sum(x-1,0,p2-1);
MaxSelf(mx,tmp);
i1++;
if(i1<sz(inds[x-2])) p1=inds[x-2][i1];
}
MaxSelf(dp[0][x][p2],mx);
i2++;
if(i2<sz(inds[x])) p2=inds[x][i2];
}
//Trazimo dp gde je pile na x-1 jednak N i na x-1 je vrh
for(int p:inds[x]){
MaxSelf(dp[2][x][p],dp[0][x-1][N]+Sum(x,p,N-1));
}
}
}
}
/*
for(int x=0;x<N;x++){
Debug(x); cerr<<":"<<endl;
for(int d=0;d<3;d++){
for(int p:inds[x]){
Debug(d,x,p,dp[d][x][p]);
}
}
cerr<<endl<<"------------------------"<<endl;
}
*/
ll res=0;
for(int p:inds[N-1]){
MaxSelf(res,MaxDP(N-1,p,{0,1,2}));
}
return res;
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
