#include <bits/stdc++.h>
using namespace std;
const int c=3000005;
int n, m, si[c];
vector<pair<int, int> > sz[c];
vector<long long> dp0[c], dp1[c];
// 0 - megkapta a felette levoket, 1 - meg nem kapta meg
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++) {
int a=X[i], b=Y[i], s=W[i];
a++, b++;
sz[a].push_back({b, s});
//cout << "alap " << a << " " << b << " " << s << "\n";
}
for (int i=1; i<=n; i++) {
sz[i].push_back({n+1, 0});
sort(sz[i].begin(), sz[i].end());
si[i]=sz[i].size();
dp0[i].resize(si[i]), dp1[i].resize(si[i]);
}
for (int i=1; i<=n; i++) {
int x=si[i-1], y=si[i];
// 0->1
long long maxi=0, sum=0, pos=0;
for (int j=0; j<x; j++) {
maxi=max(maxi, dp0[i-1][j]);
}
for (int j=0; j<y; j++) {
dp1[i][j]=maxi;
}
// 1->1
maxi=0, sum=0;
for (int j=0; j<x; j++) {
maxi=max(maxi, dp1[i-1][j]-sum);
sum+=sz[i-1][j].second;
}
sum=0;
for (int j=0; j<y; j++) {
while (pos<x && sz[i][j].first>sz[i-1][pos].first) {
sum+=sz[i-1][pos].second;
pos++;
}
dp1[i][j]=max(dp1[i][j], maxi+sum);
}
// 0->0
maxi=0, sum=0, pos=0;
for (int j=0; j<x; j++) {
while (pos<y && sz[i-1][j].first>sz[i][pos].first) {
sum+=sz[i][pos].second;
pos++;
}
maxi=max(maxi, dp0[i-1][j]+sum);
}
sum=0;
for (int j=0; j<y; j++) {
dp0[i][j]=maxi-sum;
sum+=sz[i][j].second;
}
// 1->0 olyan, csak rosszabb lehet, mint az 1->1
for (int j=0; j<y; j++) {
dp0[i][j]=max(dp0[i][j], dp1[i][j]);
}
for (int j=0; j<y; j++) {
//cout << i << " " << j << " " << dp0[i][j] << " " << dp1[i][j] << "\n";
}
}
long long maxi=0;
for (int j=0; j<si[n]; j++) {
maxi=max(maxi, dp0[n][j]);
}
return maxi;
}
/*
int main()
{
int n, m;
vector<int> a, b, c;
cin >> n >> m;
for (int i=0; i<m; i++) {
int aa, bb, cc;
cin >> aa >> bb >> cc;
a.push_back(aa), b.push_back(bb), c.push_back(cc);
}
cout << max_weights(n, m, a, b, c) << "\n";
return 0;
}
*/
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
