/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
using ull = uint64_t;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int long long
const char nl = '\n';
//const int N = 2e5+1;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int mod = 1e9+7;
struct segtree{
vector<ll> tree;
int size;
void init(int n) {
size = 1;
while (size < n)size <<= 1;
tree.assign(2*size-1, 0ll);
}
void set(int i, ll v, int x, int lx, int rx) {
if (rx-lx==1) {
tree[x] = v;
return;
}
int mid = lx+rx>>1;
if (i < mid)set(i, v, 2*x+1, lx, mid);
else set(i, v, 2*x+2, mid, rx);
tree[x] = max(tree[2*x+1], tree[2*x+2]);
}
void set(int i, ll v) {
set(i, v, 0, 0, size);
}
ll get(int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx)return 0ll;
if (lx >= l && rx <= r)return tree[x];
int mid = lx+rx>>1;
return max(get(l, r, 2*x+1, lx, mid), get(l, r, 2*x+2, mid, rx));
}
ll get(int l, int r) {
return get(l, r, 0, 0, size);
}
};
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<int> a(N+1);
for (int i = 0; i < M; ++i)a[X[i]] = W[i];
vector<ll> dp(N+1);
//dp[0] = a[0];
segtree st, st2;
st.init(N+1);
st2.init(N+1);
st2.set(0, dp[0]);
for (int i = 1; i < N; ++i) {
ll mx = 0ll, mx2 = 0ll;
if (i-2 >= 0)mx = st.get(0, i-1), mx2 = st2.get(0, i-1);
if (i+1 < N) {
st2.set(i, st.get(0, i)+a[i]);
}
dp[i] = max(mx, mx2)+a[i];
st.set(i, dp[i]);
}
return max(st.tree[0], st2.tree[0]);
}
//int main() {
//int n, m;
//cin >> n >> m;
//vector<int> x(m), y(m), w(m);
//for (int i = 0; i < m; ++i)cin >> x[i] >> y[i] >> w[i];
//cout << max_weights(n, m, x, y, w);
//}
