# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
const long long inf = 1e17;
int n,m,x[N],y[N],w[N];
vector <pii> v[N];
long long ans;
vector <long long> pot[N],pr[N],pr_dp[N],sf_dp[N], dp[N],dp_inc[N],dp_dec[N];
int go(int idx, long long val) {
int le = 0;
int ri = pot[idx].size() - 1;
int ans = - 1;
while (le <= ri) {
int mid = (le + ri) / 2;
if (pot[idx][mid] <= val) {
ans = mid;
le = mid + 1;
} else ri = mid - 1;
}
return ans;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
m = M;
n = N;
for (int i = 0; i < m; i++) {
x[i] = X[i] + 1;
y[i] = Y[i] + 1;
w[i] = W[i];
v[x[i]].pb({y[i] - 1, w[i]});
pot[x[i]].pb(y[i] - 1);
}
for (int i = 1; i <= n; i++) {
v[i].pb({0,0}); v[i].pb({n,0}); sort(v[i].begin(),v[i].end());
pot[i].pb(0); pot[i].pb(n); sort(pot[i].begin(),pot[i].end());
pr[i] = vector <long long> (v[i].size() + 5, 0);
for (int j = 0; j < v[i].size(); j++) {
pr[i][j] = pr[i][j - (j != 0)] + v[i][j].s;
}
}
/*
for (int i = 1; i <= n; i++) {
cout<<i<<" ----- > ";
for (int po : pot[i]) cout<<po<<" ";
cout<<"\n";
}*/
for (int i = 1; i <= n; i++) {
dp[i] = vector <long long> (pot[i].size() + 5, 0);
dp_inc[i] = dp_dec[i] = vector < long long > (pot[i].size() + 5, 0);
sf_dp[i] = pr_dp[i] = vector <long long> (pot[i].size() + 5, -inf);
if (i > 1) {
// if ( a >= b)
long long mx = 0;
for (int j = 0; j < v[i - 1].size(); j++) mx = max(mx, dp_inc[i - 1][j]), mx = max(mx, dp_dec[i - 1][j]);
dp_inc[i][0] = max(dp_inc[i][0], mx);
dp_dec[i][0] = max(dp_dec[i][0], mx);
for (int j = 0; j < pot[i].size(); j++) {
int a = pot[i][j];
int prid = go(i - 1, a - 1);
// dp[i][j] = dp[i - 1][k] + (pr[i - 1][j] - pr[i - 1][k])
// dp[i][j] = (dp[i - 1][k] - pr[i - 1][k]) + pr[i - 1][j]
if (prid == -1) {
dp_inc[i][j] = mx;
continue;
}
dp_inc[i][j] = max(dp_inc[i][j], pr_dp[i - 1][prid] + pr[i - 1][prid]);
}
dp_inc[i][pot[i].size() - 1] = max(dp_inc[i][pot[i].size() - 1], max(dp_inc[i - 1][pot[i - 1].size() - 1], dp_dec[i - 1][pot[i - 1].size() - 1]));
dp_dec[i][pot[i].size() - 1] = dp_inc[i][pot[i].size() - 1];
// if ( a < b )
for (int j = 0; j < pot[i].size(); j++) {
int a = pot[i][j];
int prid = go(i - 1, a - 1); prid++;
dp_dec[i][j] = max(dp_dec[i][j], sf_dp[i - 1][prid] - (j ? pr[i][j - 1] : 0)); // ?
}
}
/*for (int j = 0; j < pot[i].size(); j++) {
if (dp_dec[i][j])cout<<i<<" "<<pot[i][j]<<" "<<dp_dec[i][j]<<"\n";
}*/
if (i == n) continue;
pr_dp[i][0] = dp_inc[i][0];
for (int j = 1; j < pot[i].size(); j++) {
pr_dp[i][j] = max(pr_dp[i][j - 1], dp_inc[i][j] - pr[i][j - 1]); // j - 1
}
set <pii> s;
long long sf_sum = 0;
for (pii x : v[i + 1]) {
s.insert({x.f, x.s});
sf_sum += x.s;
}
int sz = pot[i].size();
for (int j = sz - 1; j >= 0; j--) {
while (s.size() && (*--s.end()).f >= pot[i][j]) {
sf_sum -= (*--s.end()).s;
s.erase(--s.end());
}
sf_dp[i][j] = max(sf_dp[i][j + 1], dp_dec[i][j] + sf_sum);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < pot[i].size(); j++) {
ans = max(ans, dp_inc[i][j]);
ans = max(ans, dp_dec[i][j]);
}
}
return ans;
}
/*
signed main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> X(M), Y(M), W(M);
for (int i = 0; i < M; ++i) {
assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
}
long long result = max_weights(N, M, X, Y, W);
printf("%lld\n", result);
return 0;
}*/
