一眼网络流，考虑建图。
根据贪心思想，我们最好选完所有正权点，不选所有负权点。
Trick：考虑 \(S\) 向所有正权点连边，流量为权值，所有负权点向 \(T\) 连边，流量为权值绝对值。
但他还有一些限制，就是选了这个不选那个就会减少体验值，不妨设 \((x,y,z)\) 表示选了 \(x\) 不选 \(y\) 会减少 \(z\) 的体验值，考虑 \(x\) 向 \(y\) 连边，流量为 \(z\)。
Trick：当题目这样有减少体验值，可以考虑最小割
考虑割掉 \(S\) 与正权点之间连边，表示不选这个正权点，割掉 \(x->y\) 这条边表示选 \(x\) 不选 \(y\)，割掉负权点与 \(T\) 之间连边，表示选这个负权点。
最后用所有正权点的和减去最大流就好了
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=110000,INF=1e12;
ll n,m,a[N],s,t;
ll h[N],e[N],ne[N],w[N],idx=1;
void add(ll a,ll b,ll c)
{
e[++idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx;
e[++idx]=a;
w[idx]=0;
ne[idx]=h[b];
h[b]=idx;
}
ll dep[N],now[N],ans,ans1;
bool bfs()
{
for(ll i=s;i<=t;i++) dep[i]=INF;
dep[s]=1;
queue<ll> q;
q.push(s);
now[s]=h[s];
while(!q.empty())
{
ll wz=q.front();
q.pop();
for(ll i=h[wz];i;i=ne[i])
{
ll j=e[i];
if(w[i]==0) continue;//只枚举大于0的边
if(dep[j]==INF)
{
now[j]=h[j];
dep[j]=dep[wz]+1;
q.push(j);
if(j==t) return true;
}
}
}
return false;
}
ll dfs(ll wz,ll k)
{
if(wz==t) return k;
ll sum,res=0;
for(ll i=now[wz];i&&k;i=ne[i])
{
now[wz]=i;
ll j=e[i];
if(w[i]==0||dep[j]!=dep[wz]+1) continue;
sum=dfs(j,min(k,w[i]));
if(sum==0) dep[j]=INF;
res+=sum;
k-=sum;
w[i]-=sum;
w[i^1]+=sum;
}
return res;
}
int main()
{
scanf("%lld %lld",&n,&m);
s=0,t=n+1;
for(ll i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
if(a[i]>0) add(s,i,a[i]),ans1+=a[i];
if(a[i]<0) add(i,t,-a[i]);
}
ll t1,t2,t3;
for(ll i=1;i<=m;i++)
{
scanf("%lld %lld %lld",&t1,&t2,&t3);
add(t1,t2,t3);
}
while(bfs()) ans+=dfs(s,INF);
printf("%lld\n",ans1-ans);
return 0;
}