#include <bits/stdc++.h>
using namespace std;
#include "fish.h"
int N, M;
vector<int> idx[100010];
int sz[100010];
vector<long long> sum[100010];
vector<long long> up[100010];
vector<long long> down[100010];
long long tot[100010];
void init(vector<int> &X, vector<int> &Y, vector<int> &W)
{
vector<vector<pair<int, int>>> fish(N);
for(int i = 0; i < M; i++)
fish[X[i]].push_back({ Y[i], W[i] });
for(int i = 0; i < N; i++)
{
sz[i] = (int)fish[i].size();
if(!sz[i])
continue;
sort(fish[i].begin(), fish[i].end());
idx[i].resize(sz[i]);
sum[i].resize(sz[i]);
up[i].resize(sz[i]);
down[i].resize(sz[i]);
for(int j = 0; j < sz[i]; j++)
{
auto [x, y] = fish[i][j];
idx[i][j] = x;
sum[i][j] = y;
if(j)
sum[i][j] += sum[i][j - 1];
}
}
}
long long solve()
{
tot[0] = 0;
for(int i = 0; i < sz[0]; i++)
up[0][i] = sum[0][i];
for(int i = 1; i < N; i++)
{
tot[i] = !sz[i - 1] ? tot[i - 1] : max({ tot[i - 1], down[i - 1].front(), up[i - 1].back() });
if(!sz[i])
continue;
if(!sz[i - 1])
{
down[i][0] = tot[i - 1] + sum[i].back();
continue;
}
long long mx = tot[i - 1] + sum[i].back();
int p = sz[i - 1] - 1, q = sz[i] - 1;
for(int j = sz[i] - 1; j >= 0; j--)
{
while(p >= 0 && idx[i - 1][p] > idx[i][j])
{
while(q >= 0 && idx[i][q] >= idx[i - 1][p])
q--;
mx = max(mx, down[i - 1][p] + (q >= 0 ? sum[i][q] : 0));
p--;
}
down[i][j] = mx - (j ? sum[i][j - 1] : 0);
}
mx = down[i - 1].front();
p = 0, q = 0;
for(int j = 0; j < sz[i]; j++)
{
while(p < sz[i - 1] && idx[i - 1][p] < idx[i][j])
{
while(q < sz[i] && idx[i][q] <= idx[i - 1][p])
q++;
mx = max(mx, up[i - 1][p] - (q ? sum[i][q - 1] : 0));
p++;
}
up[i][j] = mx + sum[i][j];
}
}
long long res = tot[N - 1];
if(sz[N - 1])
res = max(res, down[N - 1].front());
return res;
}
long long max_weights(int _N, int _M, vector<int> X, vector<int> Y, vector<int> W)
{
N = _N;
M = _M;
init(X, Y, W);
return solve();
}
