#include<bits/stdc++.h>
#include <vector>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M = 1e6 + 10;
const int N = 3e5 + 10;
const int mod = 1e9 + 7;
int n, m;
long long t[2][2][4 * N], lz[2][2][4 * N];
void add(int cur, int tt, int s, long long val)
{
t[cur][tt][s] += val;
lz[cur][tt][s] += val;
}
void lazy(int cur, int tt, int s)
{
add(cur, tt, s * 2, lz[cur][tt][s]);
add(cur, tt, s * 2 + 1, lz[cur][tt][s]);
lz[cur][tt][s] = 0;
}
void upd(int cur, int tt, int s, int l, int r, int u, int v, long long val)
{
if(u > r || v < l) return ;
if(u <= l && r <= v) {
add(cur, tt, s, val);
return ;
}
int mid = (l + r)/2;
if(l != r && lz[cur][tt][s] != 0) lazy(cur,tt,s);
upd(cur, tt, s * 2, l, mid, u, v, val);
upd(cur, tt, s * 2 + 1, mid + 1, r, u, v, val);
t[cur][tt][s] = max(t[cur][tt][s * 2], t[cur][tt][s * 2 + 1]);
}
long long get(int cur,int tt,int s, int l, int r,int u,int v)
{
if(u > r || v < l) return 0;
if(u <= l && r <= v) return t[cur][tt][s];
int mid = (l + r)/2;
if(l != r && lz[cur][tt][s] != 0) lazy(cur,tt,s);
return max(get(cur, tt, s * 2, l, mid, u, v), get(cur, tt, s * 2 + 1, mid + 1, r, u, v));
}
vector<ii> Q[N];
long long f[2][2][N];
long long max_weights(int N, int M,std::vector<int> X ,std::vector<int> Y ,std::vector<int> W )
{
n = N;
m = M;
for(int i = 1;i <= n; i++) Q[i].pb({0,0});
for(int i = 0;i < m; i++) {
X[i]++;
Y[i]++;
Q[X[i]].pb({Y[i],W[i]});
}
for(int i = 1;i <= n; i++) sort(Q[i].begin(), Q[i].end());
for(int i = 1;i <= n; i++) {
int u = Q[i].back().first;
if(u != n) Q[i].pb({n,0});
}
int pre, cur;
for(int i = 2;i <= n; i++) {
//
pre = i - 1 & 1, cur = i & 1;
for(auto[pos,val] : Q[i]) {
upd(pre, 0, 1, 0, n, pos, n, val);
upd(pre, 1, 1, 0, n, pos, n, val);
}
for(auto[pos,val] : Q[i]) {
if(pos != 0 && f[cur][1][pos - 1] == 0) {
int x = max(get(pre, 0, 1, 0, n, pos - 1, n), get(pre, 1, 1, 0, n, pos - 1, n));
upd(cur, 1, 1, 0, n, pos - 1, pos - 1, x);
f[cur][1][pos - 1] = x;
}
upd(pre, 0, 1, 0, n, pos, n, -val);
upd(pre, 1, 1, 0, n, pos, n, -val);
int x = max(get(pre, 0, 1, 0, n, pos, n), get(pre, 1, 1, 0, n, pos, n));
upd(cur, 1, 1, 0, n, pos, pos, x);
f[cur][1][pos] = x;
//cout << i << " " << 1 << " " << pos << " " << x << "\n";
}
//
for(auto [pos,val] : Q[i - 1]) {
upd(pre, 0, 1, 0, n, 0, pos - 1, val);
//if(i == 2) cerr << val << " " << pos << "\n";
}
reverse(Q[i - 1].begin(), Q[i - 1].end());
for(auto [pos,val] : Q[i - 1]) {
int x = max(get(pre, 0, 1, 0, n, 0, pos),get(pre, 1, 1, 0, n, 0, pos));
upd(cur, 0, 1, 0, n, pos, pos, x);
f[cur][0][pos] = x;
//cout << i << " " << 0 << " " << pos << " " << x << "\n";
upd(pre, 0, 1, 0, n, 0, pos - 1, -val);
}
reverse(Q[i - 1].begin(), Q[i - 1].end());
for(auto[pos,val] : Q[i - 1]) {
upd(pre, 1, 1, 0, n, pos, pos, -f[pre][1][pos]);
f[pre][1][pos] = 0;
if(pos != 0 && f[pre][1][pos - 1] != 0) {
upd(pre, 1, 1, 0, n, pos - 1, pos - 1, -f[pre][1][pos - 1]);
f[pre][1][pos - 1] = 0;
}
}
if(i != 2) {
for(auto[pos,val] : Q[i - 2]) {
upd(pre, 0, 1, 0, n, pos, pos, -f[pre][0][pos]);
f[pre][0][pos] = 0;
}
}
}
long long kq = max(t[n & 1][0][1],t[n & 1][1][1]);
return kq;
}
