#include "fish.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll inf = 3e18;

struct SegmentTree {
    vector<ll> t, tag;
    int sz = 1;

    void init(int n) {
        sz = 1 << __lg(n) + !!(n & (n - 1));
        t.assign(sz << 1, -3e18), tag.assign(sz << 1, -3e18);
    }

    void apply(int x, ll tg) {
        t[x] = max(t[x], tg);
        tag[x] = max(tag[x], tg);
    }

    void push(int x) {
        if (tag[x] > 0) {
            apply(x << 1, tag[x]);
            apply(x << 1 | 1, tag[x]);
            tag[x] = -3e18;
        }
    }

    void pull(int x) {
        t[x] = max(t[x << 1], t[x << 1 | 1]);
    }

    ll rangeMax(int l, int r, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return -3e18;
        }
        if (l <= lx && rx <= r) {
            return t[x];
        }
        int mid = lx + rx >> 1;
        push(x);
        return max(rangeMax(l, r, x << 1, lx, mid), rangeMax(l, r, x << 1 | 1, mid, rx));
    }

    ll rangeMax(int l, int r) {
        return rangeMax(l, r, 1, 0, sz);
    }

    void rangeApply(int l, int r, ll tg, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return;
        }
        if (l <= lx && rx <= r) {
            return apply(x, tg);
        }
        int mid = lx + rx >> 1;
        push(x);
        rangeApply(l, r, tg, x << 1, lx, mid);
        rangeApply(l, r, tg, x << 1 | 1, mid, rx);
        pull(x);
    }

    void rangeApply(int l, int r, ll tg) {
        rangeApply(l, r, tg, 1, 0, sz);
    }
};

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    SegmentTree t[2];
    t[0].init(N + 1), t[1].init(N + 1);
    t[0].rangeApply(0, 1, 0), t[1].rangeApply(0, 1, 0);
    
    vector<vector<pair<int, int>>> adj(N + 3);
    for (int i = 0; i < M; ++i) {
        adj[X[i]].push_back({Y[i] + 1, W[i]});    
    }

    for (int x = 0; x <= N + 2; ++x) {
        sort(adj[x].begin(), adj[x].end());
        if (x > 0) {
            vector<ll> p{-inf};
            for (auto [y, add] : adj[x - 1]) {
                p.push_back(add + max(p.back(), t[0].rangeMax(0, y)));
            }
            int i = 0;
            for (auto [y, add] : adj[x - 1]) {
                t[0].rangeApply(y, N + 1, p[++i]);
            }
        }
        t[0].rangeApply(0, 1, t[1].rangeMax(0, 1));
        t[1].rangeApply(N, N + 1, t[0].rangeMax(N, N + 1));
        reverse(adj[x].begin(), adj[x].end());
        vector<ll> p{-inf};
        for (auto [y, add] : adj[x]) {
            p.push_back(add + max(p.back(), t[1].rangeMax(y, N + 1)));
        }
        int i = 0;
        for (auto [y, add] : adj[x]) {
            t[1].rangeApply(0, y, p[++i]);
        }
        // cout << "dp[0]: ";
        // for (int i = 0; i <= N; ++i) {
        //     cout << t[0].rangeMax(i, i + 1) << " ";
        // }
        // cout << endl;
        // cout << "dp[1]: ";
        // for (int i = 0; i <= N; ++i) {
        //     cout << t[1].rangeMax(i, i + 1) << " ";
        // }
        // cout << endl;
    }

    return max(t[0].rangeMax(0, N + 1), t[1].rangeMax(0, N + 1));
}