#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
long long int a,b,c;
};
bool cmp(cell a1,cell a2)
{
if(a1.b<a2.b)return true;
if(a1.b>a2.b)return false;
return a1.a<a2.a;
}
struct cord
{
long long int i,st;
};
long long int n,m;
long long int otg,ultdp[100005],mdp[100005];
///long long int dp[3005][3005],rdp[3005][3005],sdp[3005][3005],col[3005][3005],mat[3005][3005];
vector<cord>dp[100005],rdp[100005],sdp[100005],col[100005],mat[100005];
cell a[300005];
/**
void make_dp()
{
long long int ma1=0,ma2=0,use1=0,use2=0,l1=0;
for(int j=1;j<=n;j++)
{
ma1=0;
if(j>=2)ma2=0;
use1=mdp[j-1];
use2=mdp[j-2];
l1=0;
for(int i=1;i<=n;i++)
{
ma1+=mat[i][j-1];
ma1=max(ma1,sdp[i][j-1]);
if(j>=2)
{
ma2+=mat[i][j-1];
ma2=max(ma2,rdp[i][j-2]);
}
if(!l1)use1-=mat[i][j];
if(ma1>=use1)
{
use1=ma1;
l1=1;
}
if(ma2>=use2)
{
use2=ma2;
}
if(j>=3)dp[i][j]=ultdp[j-3]+col[i][j-1]+col[i][j+1];
else dp[i][j]=col[i][j-1]+col[i][j+1];
dp[i][j]=max(dp[i][j],use1+col[i][j+1]);
dp[i][j]=max(dp[i][j],use2+col[i][j+1]);
sdp[i][j]=max(ma1,rdp[i][j-1]);
sdp[i][j]=max(sdp[i][j],use2);
sdp[i][j]=max(sdp[i][j],ultdp[j-3]+col[i][j-1]);
rdp[i][j]=dp[i][j]-col[i][j+1];
mdp[j]=max(mdp[j],dp[i][j]);
otg=max(otg,dp[i][j]);
}
ultdp[j]=max(ultdp[j],mdp[j]);
}
//cout<<endl;
for(int i=n;i>=1;i--)
{
for(int j=1;j<=n;j++)
{
//cout<<dp[i][j]<<" ";
}
//cout<<endl;
}
}
**/
void prime_dp()
{
long long int ma1,ma2,use1,use2;
int i,z1,z2,zm1,zm2,zm3,l;
for(int j=1;j<=n;j++)
{
ma1=0;
ma2=0;
use1=mdp[j-1];
use2=mdp[j-2];
l=0;
z1=0;
z2=0;
zm1=0;
zm2=0;
zm3=0;
for(int z=0;z<dp[j].size();z++)
{
///FIX zm and mat
i=dp[j][z].i;
zm1++;
while(zm1<mat[j-1].size()&&mat[j-1][zm1].i<=i)
{
ma1+=mat[j-1][zm1].st;
ma2+=mat[j-1][zm1].st;
zm1++;
}
zm2++;
while(zm2<mat[j].size()&&mat[j][zm2].i<=i)
{
if(!l)use1-=mat[j][zm2].st;
zm2++;
}
zm3++;
while(zm3<mat[j+1].size()&&mat[j+1][zm3].i<=i)
{
zm3++;
}
zm1=max(0,zm1-1);
zm2=max(0,zm2-1);
zm3=max(0,zm3-1);
///FIX ma and use
z1++;
while(z1<dp[j-1].size()&&dp[j-1][z1].i<=i)
{
ma1=max(ma1,sdp[j-1][z1].st);
z1++;
}
z2++;
while(z2<dp[j-2].size()&&dp[j-2][z2].i<=i)
{
ma2=max(ma2,rdp[j-2][z2].st);
z2++;
}
z1--;
z2--;
if(ma1>=use1)
{
use1=ma1;
l=1;
}
if(ma2>=use2)
{
use2=ma2;
}
///FIX all dp
if(j>=3)dp[j][z].st=ultdp[j-3]+col[j-1][zm1].st+col[j+1][zm3].st;
else dp[j][z].st=col[j-1][zm1].st+col[j+1][zm3].st;
dp[j][z].st=max(dp[j][z].st,use1+col[j+1][zm3].st);
dp[j][z].st=max(dp[j][z].st,use2+col[j+1][zm3].st);
sdp[j][z].st=max(ma1,rdp[j-1][z1].st);
sdp[j][z].st=max(sdp[j][z].st,use2);
if(j>=3)sdp[j][z].st=max(sdp[j][z].st,ultdp[j-3]+col[j-1][zm1].st);
else sdp[j][z].st=max(sdp[j][z].st,col[j-1][zm1].st);
rdp[j][z].st=dp[j][z].st-col[j+1][zm3].st;
mdp[j]=max(mdp[j],dp[j][z].st);
otg=max(otg,dp[j][z].st);
//cout<<j<<" "<<i<<" "<<dp[j][z].st<<" "<<use1<<" "<<sdp[j][z].st<<endl;
}
ultdp[j]=max(ultdp[j-1],mdp[j]);
}
}
void prec()
{
cord c;
c.i=0;
c.st=0;
for(int i=0;i<=n+1;i++)
{
dp[i].push_back(c);
rdp[i].push_back(c);
sdp[i].push_back(c);
mat[i].push_back(c);
col[i].push_back(c);
}
for(int i=1;i<=m;i++)
{
c.i=a[i].a;
c.st=a[i].c;
if(a[i].b!=1&&(dp[a[i].b-1].size()==0||dp[a[i].b-1].back().i<c.i))
{
dp[a[i].b-1].push_back(c);
rdp[a[i].b-1].push_back(c);
sdp[a[i].b-1].push_back(c);
}
dp[a[i].b+1].push_back(c);
rdp[a[i].b+1].push_back(c);
sdp[a[i].b+1].push_back(c);
mat[a[i].b].push_back(c);
if(col[a[i].b].size())c.st+=col[a[i].b].back().st;
col[a[i].b].push_back(c);
}
/*cout<<endl;
for(int j=1;j<=n;j++)
{
cout<<j<<" ";
for(int z=0;z<col[j].size();z++)
{
cout<<col[j][z].st<<" ";
}
cout<<endl;
}*/
}
long long int max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
n=N;
m=M;
for(int i=1;i<=m;i++)
{
a[i].a=Y[i-1]+1;
a[i].b=X[i-1]+1;
a[i].c=W[i-1];
}
sort(a+1,a+m+1,cmp);
prec();
prime_dp();
///make_dp();
return otg;
}
