#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long) 1e18;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector< vector< pair<int, long long> > > x(N + 1);
for (int i = 0; i < M; i++) {
x[X[i] + 1].push_back({Y[i], W[i]});
}
for (int i = 0; i <= N; i++) {
x[i].push_back({-1, 0});
sort(x[i].begin(), x[i].end());
for (int j = 1; j < (int) x[i].size(); j++) x[i][j].second += x[i][j - 1].second;
}
vector< vector<int> > pos(N + 1);
pos[0] = {0};
for (int i = 1; i <= N; i++) {
for (auto &p : x[i - 1]) pos[i].push_back(p.first + 1);
if (i < N) for (auto &p : x[i + 1]) pos[i].push_back(p.first + 1);
sort(pos[i].begin(), pos[i].end());
pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
}
vector< vector< vector<long long> > > dp(N + 1);
dp[0] = {{0, 0}};
for (int i = 1; i <= N; i++) {
dp[i].assign((int) pos[i].size(), vector<long long>(2, -INF));
int ptr_h = 0, ptr_k = 0, ptr_h_2 = 0;
long long mx = -INF;
for (int j = 0; j < (int) pos[i].size(); j++) {
int h = pos[i][j];
while (ptr_h < (int) pos[i - 1].size() && pos[i - 1][ptr_h] <= h) {
while (ptr_k < (int) x[i - 1].size() && x[i - 1][ptr_k].first < pos[i - 1][ptr_h]) ptr_k++;
mx = max(mx, dp[i - 1][ptr_h][0] - (ptr_k > 0 ? x[i - 1][ptr_k - 1].second : 0));
ptr_h++;
}
while (ptr_h_2 < (int) x[i - 1].size() && x[i - 1][ptr_h_2].first < h) ptr_h_2++;
dp[i][j][0] = max(mx + (ptr_h_2 > 0 ? x[i - 1][ptr_h_2 - 1].second : 0), dp[i - 1][0][1]);
}
ptr_h = (int) pos[i - 1].size() - 1, ptr_k = (int) x[i].size() - 1,
ptr_h_2 = (int) x[i].size() - 1, mx = -INF;
for (int j = (int) pos[i].size() - 1; j >= 0; j--) {
int h = pos[i][j];
while (ptr_h >= 0 && pos[i - 1][ptr_h] >= h) {
while (ptr_k >= 0 && x[i][ptr_k].first >= pos[i - 1][ptr_h]) ptr_k--;
mx = max(mx, dp[i - 1][ptr_h][0] + (ptr_k >= 0 ? x[i][ptr_k].second : 0));
mx = max(mx, dp[i - 1][ptr_h][1] + (ptr_k >= 0 ? x[i][ptr_k].second : 0));
ptr_h--;
}
while (ptr_h_2 >= 0 && x[i][ptr_h_2].first >= h) ptr_h_2--;
dp[i][j][1] = mx - (ptr_h_2 >= 0 ? x[i][ptr_h_2].second : 0);
}
}
long long ans = 0;
for (int j = 0; j < (int) dp[N].size(); j++) ans = max({ans, dp[N][j][0], dp[N][j][1]});
return ans;
}
