#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
vector<vector<pi>> occ(n + 1);
for (int i = 0; i < m; ++i) {
occ[x[i]].push_back({y[i], w[i]});
}
for (int i = 0; i < n; ++i) occ[i].push_back({n, 0});
for (int i = 0; i < n; ++i) sort(occ[i].begin(), occ[i].end());
auto between = [&](int x, int l, int r) {
ll ans = 0;
for (auto [a, b] : occ[x]) if (l <= a && a <= r) ans += b;
return ans;
};
vector<vector<ll>> dp0(n + 1), dp1(n);
for (int i = 0; i < n; ++i) dp0[i].assign(occ[i].size(), 0);
for (int i = 0; i < n; ++i) dp1[i].assign(occ[i].size(), 0);
for (int i = 1; i < n; ++i) {
// p[i] < p[i - 1]
for (int j = 0; j < occ[i].size(); ++j) {
for (int k = 0; k < occ[i - 1].size(); ++k) {
if (occ[i - 1][k].F - 1 >= occ[i][j].F) {
ckmax(dp0[i][j], dp0[i - 1][k] + between(i, occ[i][j].F, occ[i - 1][k].F - 1));
ckmax(dp0[i][j], dp1[i - 1][k] + between(i, occ[i][j].F, occ[i - 1][k].F - 1));
}
}
}
// p[i] > p[i - 1]
for (int j = 0; j < occ[i].size(); ++j) {
for (int k = 0; k < occ[i - 1].size(); ++k) {
if (occ[i - 1][k].F - 1 <= occ[i][j].F - 1) {
ckmax(dp1[i][j], dp1[i - 1][k] + between(i - 1, occ[i - 1][k].F, occ[i][j].F - 1));
}
}
if (i >= 2) {
for (int k = 0; k < occ[i - 2].size(); ++k) {
ckmax(dp1[i][j], dp0[i - 2][k] + between(i - 1, 0, max(occ[i][j].F - 1, occ[i - 1][k].F - 1)));
ckmax(dp1[i][j], dp1[i - 2][k] + between(i - 1, 0, max(occ[i][j].F - 1, occ[i - 1][k].F - 1)));
}
}
}
}
ll ans = 0;
for (int i = 0; i < occ[n - 1].size(); ++i) ckmax(ans, dp0[n - 1][i]);
for (int i = 0; i < occ[n - 1].size(); ++i) ckmax(ans, dp1[n - 1][i]);
return ans;
}
