#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i) 
#define R(i, j, k) for(int i = (j); i >= (k); --i) 
#define ll long long 
#define vi vector < int > 
#define sz(a) ((int) (a).size())
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1e6 + 7;
int n, m;

struct segt {
	ll mx[N];
	void upd(int x) { mx[x] = max(mx[x << 1], mx[x << 1 | 1]); }
	void Add(int x, int L, int R, int p, ll w) {
		if(L == R) return mx[x] = max(mx[x], w), void();
		int mid = (L + R) >> 1;
		p <= mid ? Add(x << 1, L, mid, p, w) : Add(x << 1 | 1, mid + 1, R, p, w), upd(x); 
	}
	ll Query(int x, int L, int R, int l, int r) {
		if(l <= L && R <= r) return mx[x];
		ll ns = -1e18;
		int mid = (L + R) >> 1;
		if(l <= mid) ns = max(ns, Query(x << 1, L, mid, l, r));
		if(r > mid) ns = max(ns, Query(x << 1 | 1, mid + 1, R, l, r));
		return ns;
	}
	void ins(int x, ll w) {
		Add(1, 0, n + 1, x, w);
	}
	ll get(int l, int r) {
		return Query(1, 0, n, l, r);
	} 
	void build(int x, int L, int R) {
		if(L == R) return ;
		mx[x] = -1e18;
		int mid = (L + R) >> 1;
		build(x << 1, L, mid);
		build(x << 1 | 1, mid + 1, R);
	}
} a, b;

/*
a : up
b : down
*/

vector < pair < int, int > > pr[N];
ll A[N], B[N], F[N], bc[N];

void case1(int x) { // a transform. 
	sort(pr[x].begin(), pr[x].end());
	for(auto u : pr[x]) {
		a.ins(u.first + 1, a.get(0, u.first) + u.second);
	}
	cout << "bc = " << bc[x] << '\n';
	L(i, 0, n)
		a.ins(i, bc[x]);
}
void case2(int x) {
	sort(pr[x + 1].begin(), pr[x + 1].end());
	reverse(pr[x + 1].begin(), pr[x + 1].end());
	for(auto u : pr[x + 1]) {
		ll dwn = b.get(u.first + 1, n) + u.second;
		bc[x + 1] = max(bc[x + 1], dwn);
		b.ins(u.first, dwn);
	}
}
ll S[N];

ll max_weights(int xn, int xm, vi x, vi y, vi z) {
	n = xn, m = xm;
	L(i, 0, m - 1) pr[x[i]].push_back({y[i], z[i]}), S[x[i]] += y[i];
	a.build(1, 0, n);
	b.build(1, 0, n);
	a.ins(0, 0);
	L(i, 0, n) {
		ll upd = b.get(0, n);
		b.ins(n, a.get(0, n)), case1(i), case2(i), a.ins(0, upd);
		b.ins(n, a.get(0, n));
	}
	return a.get(0, 0);
}