#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const ll N=1e5+5;
int n,m,sz[N];
vector<ll>dp[2][N];
vector<pair<int,int>>f[N];
ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W){
n=N,m=M;
for(int i=0;i<n;i++){
f[i].pb({0,0});
}
for(int i=0;i<m;i++){
f[X[i]].pb({Y[i],W[i]});
}
for(int i=0;i<n;i++){
f[i].pb({n,0});
}
for(int i=0;i<n;i++){
sort(all(f[i]));
sz[i]=f[i].size();
dp[0][i].resize(sz[i]);
dp[1][i].resize(sz[i]);
fill(all(dp[0][i]),0);
fill(all(dp[1][i]),0);
}
ll ans=0;
for(int i=1;i<n;i++){
ll mx=0;
for(ll x:dp[0][i-1]){
mx=max(mx,x);
}
for(ll x:dp[1][i-1]){
mx=max(mx,x);
}
ll val_up=0;
int k=0;
// ihseh uyed
for(int j=0;j<sz[i];j++){
while(k<sz[i-1]&&f[i-1][k].ff<f[i][j].ff){
val_up=max(val_up,dp[0][i-1][k]);
val_up+=f[i-1][k].ss;
k++;
}
dp[0][i][j]=max(dp[0][i][j],max(mx,val_up));
}
// bagasah uyed
ll val_down=0;
k=sz[i-1]-1;
for(int j=sz[i]-1;j>=0;j--){
while(k>=0&&f[i-1][k].ff>f[i][j].ff){
val_down=max(val_down,dp[0][i-1][k]);
val_down=max(val_down,dp[1][i-1][k]);
k--;
}
val_down+=f[i][j].ss;
dp[1][i][j]=max(dp[1][i][j],max(mx,val_down));
}
}
for(ll j=0;j<sz[n-1];j++){
ans=max({ans,dp[0][n-1][j],dp[1][n-1][j]});
}
return ans;
}
