#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>>> col(N);
for (int i = 0; i < M; ++i) col[X[i]].push_back({Y[i], W[i]});
vector<vector<int>> vals(N);
for (int x = 0; x < N; ++x) {
vals[x].push_back(0);
vals[x].push_back(N);
for (auto [y, w] : col[x]) {
vals[x].push_back(y);
vals[x].push_back(y + 1);
}
if (x > 0) {
for (auto [y, w] : col[x - 1]) {
vals[x].push_back(y);
vals[x].push_back(y + 1);
}
}
if (x + 1 < N) {
for (auto [y, w] : col[x + 1]) {
vals[x].push_back(y);
vals[x].push_back(y + 1);
}
}
sort(vals[x].begin(), vals[x].end());
vals[x].erase(unique(vals[x].begin(), vals[x].end()), vals[x].end());
}
auto gain = [&](int x, int h, int l, int r) -> long long {
long long res = 0;
int mx = max(l, r);
for (auto [y, w] : col[x]) {
if (h <= y && mx > y) res += w;
}
return res;
};
const long long NEG = -(1LL << 60);
if (N == 1) return 0;
vector<vector<long long>> dp_prev(vals[0].size(), vector<long long>(vals[1].size(), 0));
for (int x = 1; x < N - 1; ++x) {
vector<vector<long long>> dp_next(vals[x].size(), vector<long long>(vals[x + 1].size(), NEG));
for (int i = 0; i < (int)vals[x - 1].size(); ++i) {
int hl = vals[x - 1][i];
for (int j = 0; j < (int)vals[x].size(); ++j) {
long long cur = dp_prev[i][j];
if (cur <= NEG / 2) continue;
int h = vals[x][j];
for (int k = 0; k < (int)vals[x + 1].size(); ++k) {
int hr = vals[x + 1][k];
long long v = cur + gain(x, h, hl, hr);
if (v > dp_next[j][k]) dp_next[j][k] = v;
}
}
}
dp_prev.swap(dp_next);
}
long long ans = 0;
if (N == 2) {
for (int i = 0; i < (int)vals[0].size(); ++i) {
for (int j = 0; j < (int)vals[1].size(); ++j) {
ans = max(ans, gain(0, vals[0][i], 0, vals[1][j]) +
gain(1, vals[1][j], vals[0][i], 0));
}
}
return ans;
}
for (int i = 0; i < (int)vals[N - 2].size(); ++i) {
for (int j = 0; j < (int)vals[N - 1].size(); ++j) {
ans = max(ans, dp_prev[i][j] + gain(N - 1, vals[N - 1][j], vals[N - 2][i], 0));
}
}
return ans;
}
