#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
#ifdef ONLINE_JUDGE
#include "fish.h"
#endif // ONLINE_JUDGE
const long long INF = 1e16;
long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<pair<int, int>>> f(n);
vector<int> sz(n);
vector<vector<long long>> dp_up(n), dp_down(n);
for(int i = 0; i < n; ++i) f[i].emplace_back(0, 0);
for(int i = 0; i < m; ++i) f[X[i]].emplace_back(Y[i], W[i]);
for(int i = 0; i < n; ++i) f[i].emplace_back(n, 0);
for(int i = 0; i < n; i++) {
sort(f[i].begin(), f[i].end());
sz[i] = f[i].size();
dp_down[i].assign(sz[i], 0);
dp_up[i].assign(sz[i], 0);
}
long long ans = 0;
for(int i = 1; i < n; i++) {
long long mx = 0;
for(long long x : dp_up[i - 1]) {
mx = max(mx, x);
}
for(long long x : dp_down[i - 1]) {
mx = max(mx, x);
}
long long val_up = 0;
int k = 0;
for(int j = 0; j < sz[i]; j++) {
while(k < sz[i - 1] && f[i - 1][k].first < f[i][j].first) {
val_up = max(val_up, dp_up[i - 1][k]);
val_up += f[i - 1][k].second;
k++;
}
dp_up[i][j] = max(dp_up[i][j], max(mx, val_up));
}
long long val_down = 0;
k = sz[i - 1] - 1;
for(int j = sz[i] - 1; j >= 0; j--) {
while(k >= 0 && f[i - 1][k].first > f[i][j].first) {
val_down = max(val_down, dp_up[i - 1][k]);
val_down = max(val_down, dp_down[i - 1][k]);
k--;
}
val_down += f[i][j].second;
dp_down[i][j] = max(dp_down[i][j], max(mx, val_down));
}
}
for(long long j = 0; j < sz[n - 1]; j++) {
ans = max({ans, dp_up[n - 1][j], dp_down[n - 1][j]});
}
return ans;
}
#ifndef ONLINE_JUDGE
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// file("A") else file("task");
cout << max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3}) << '\n';
return 0;
}
#endif
