#include <bits/stdc++.h>
using namespace std;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<pair<int, int>>> fish(N);
for (int i = 0; i < M; ++i) fish[X[i]].push_back({Y[i], W[i]});
const long long NEG = -(1LL << 60);
vector<vector<int>> vals(N);
for (int c = 0; c < N; ++c) {
vals[c].push_back(0);
vals[c].push_back(N);
for (auto [y, w] : fish[c]) {
vals[c].push_back(y);
vals[c].push_back(y + 1);
}
if (c > 0) {
for (auto [y, w] : fish[c - 1]) {
vals[c].push_back(y);
vals[c].push_back(y + 1);
}
}
if (c + 1 < N) {
for (auto [y, w] : fish[c + 1]) {
vals[c].push_back(y);
vals[c].push_back(y + 1);
}
}
sort(vals[c].begin(), vals[c].end());
vals[c].erase(unique(vals[c].begin(), vals[c].end()), vals[c].end());
}
auto gain = [&](int c, int left, int mid, int right) -> long long {
if (c < 0 || c >= N) return 0;
int mx = max(left, right);
long long res = 0;
for (auto [y, w] : fish[c]) {
if (mid <= y && y < mx) res += w;
}
return res;
};
vector<long long> dp_prev(vals[0].size(), 0), dp_cur;
for (int c = 1; c < N; ++c) {
int A = (int)vals[c - 1].size();
int B = (int)vals[c].size();
dp_cur.assign(B, NEG);
for (int i = 0; i < A; ++i) {
int h_prev = vals[c - 1][i];
long long base = dp_prev[i];
for (int j = 0; j < B; ++j) {
int h_cur = vals[c][j];
long long add = gain(c - 1, c - 2 >= 0 ? 0 : 0, h_prev, h_cur);
dp_cur[j] = max(dp_cur[j], base + add);
}
}
dp_prev.swap(dp_cur);
}
long long ans = 0;
int last = N - 1;
for (int i = 0; i < (int)vals[last].size(); ++i) {
ans = max(ans, dp_prev[i] + gain(last, vals[last > 0 ? last - 1 : last][0], vals[last][i], 0));
}
return ans;
}
