#include <bits/stdc++.h>
#ifndef LOCAL
#include <fish.h>
#endif // LOCAL
using namespace std;
#define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i)
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true; return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true; return false;
}
using ll = long long;
using ld = long double;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }
const int MAX = 3e5 + 5;
int n, m;
struct fish{
int x, y, w;
} fishes[MAX];
namespace subtask1{
bool check(){
rep(i, 0, m) if(fishes[i].x& 1) return false;
return true;
}
ll solve(){
ll sum = 0;
rep(i, 0, m){
if((i > 0) || (i < n - 1)){
sum += fishes[i].w;
}
}
return sum;
}
}
namespace subtask2{
bool check(){
for(int i = 0; i < m; ++i){
if(fishes[i].x > 1) return false;
}
return true;
}
ll sum[3][MAX];
ll f[3][MAX], g[3][MAX];
ll solve(){
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
rep(i, 0, m){
sum[fishes[i].x][fishes[i].y] += fishes[i].w;
}
rep(i, 0, 2){
rep(j, 0, n){
sum[i][j] += (j > 0 ? sum[i][j - 1] : 0);
}
}
ll ans = max(sum[0][n - 1], sum[1][n - 1]);
if(n > 2){
rep(i, 0, n){
maximize(ans, sum[1][n - 1] - sum[1][i] + sum[0][i]);
}
}
return ans;
}
}
namespace subtask3{
bool check(){
rep(i, 0, m){
if(fishes[i].y > 0) return false;
}
return true;
}
ll dp[MAX], s[MAX];
ll solve(){
rep(i, 0, m) s[fishes[i].x] = fishes[i].w;
dp[0] = 0;
ll res = 0;
rep(i, 1, n){
dp[i] = max(dp[i - 1], s[i - 1]);
if(i >= 2) maximize(dp[i], dp[i - 2] + s[i - 1]);
if(i >= 3) maximize(dp[i], dp[i - 3] + s[i - 2] + s[i - 1]);
maximize(res, dp[i] + s[i + 1]);
}
return res;
}
}
namespace subtask45{
bool check(){
return n <= 300;
}
ll pref[305][305];
ll solve(){
rep(i, 0, m){
pref[fishes[i].x + 1][fishes[i].y + 1] += fishes[i].w;
}
FOR(i, 1, n){
FOR(j, 1, n){
pref[i][j] += pref[i][j - 1];
}
}
vector<vector<ll>> f(n + 1, vector<ll>(n + 1));
vector<vector<ll>> g(n + 1, vector<ll>(n + 1));
/*
let f[c][r] = the maximum sum of weights if we put a pier (c, r) but we don't consider the fishes (c, r') with r' >= r
g[c][r] = the maximum sum of weights if we put a pier (c, r) but we consider the fishes (c, r') with r' >= r
let R[i] the height of pier on column c the we put
consider when R[i - 1] < R[i] -> it contributes to f[c][r]
consider when R[i - 1] > R[i] -> it contributes to g[c][r]
when calculating f[c][r] :
- consider R[i - 2] > R[i - 1] < R[i]
- consider R[i - 2] < R[i - 1] < R[i]
*/
FOR(c, 2, n){
FOR(r, 1, n){
FOR(k, 0, r){
maximize(f[c][r], f[c - 1][k] + pref[c - 1][r] - pref[c - 1][k]);
// cout << dbg(c) << dbg(r) << dbg(f[c - 1][k] + pref[c - 1][r] + pref[c - 1][k]) << '\n';
}
if(c > 2){
FOR(k, 0, n){
maximize(f[c][r], max(f[c - 2][r], g[c - 2][r]) + pref[c - 1][max(r, k)]);
// cout << dbg(c) << dbg(r) << dbg(max(f[c - 2][r], g[c - 2][r]) + pref[c - 1][max(r, k)]) << '\n';
}
}
FOR(k, r, n){
maximize(g[c][r], max(f[c - 1][k], g[c - 1][k]) + pref[c][k] - pref[c][r]);
// cout<< dbg(c) << dbg(r) << dbg(max(f[c - 1][k], g[c - 1][k]) + pref[c][k] - pref[c][r]) << '\n';
}
}
}
ll ans = 0;
FOR(c, 1, n){
FOR(r, 1, n){
maximize(ans, max(f[c][r], g[c][r]));
}
}
cerr << "subtask 4, 5 : ";
return ans;
}
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
n = N;
m = M;
rep(i, 0, M) fishes[i] = {X[i], Y[i], W[i]};
if(subtask1::check()) return subtask1::solve();
if(subtask2::check()) return subtask2::solve();
if(subtask3::check()) return subtask3::solve();
if(subtask45::check()) return subtask45::solve();
return -1;
}
#ifdef LOCAL
int main(){
cout << max_weights(2, 2, {0, 0}, {0, 1}, {4, 5}) << '\n'; //sub1
cout << max_weights(3, 2, {0, 1}, {0, 1}, {4, 5}) << '\n'; //sub2
cout << max_weights(5, 3, {2, 4, 1}, {0, 0, 0}, {4, 5, 8}) << '\n'; //sub3
cout << max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3}) << '\n';
}
#endif // LOCAL
