这道题是上一题的数据加强版，dinic表示毫无压力；
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
const int maxn=;
const int inf=;
const int s=,t=;
struct node{
int y,next,flow,re;
}e[maxn*];
int linkk[maxn*],len=,n,m,w[maxn],sum=;
void print(int x){printf("%d\n",x);}
void print(int x,int y){printf("%d %d\n",x,y);}
void insert(int x,int y,int flow){
e[++len].y=y;e[len].flow=flow;
e[len].next=linkk[x];linkk[x]=len;e[len].re=len+;
e[++len].y=x;e[len].flow=;
e[len].next=linkk[y];linkk[y]=len;e[len].re=len-;
}
void init(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&w[i]);
int x,y,v;
for(int i=;i<=m;i++){
scanf("%d%d%d",&x,&y,&v);sum+=v;
insert(s,i,v);insert(i,m+x,inf);insert(i,m+y,inf);
}
for(int i=;i<=n;i++)insert(m+i,t,w[i]);
}
int q[maxn],tail=,level[maxn],head=;
bool bfs(){
memset(level,-,sizeof(level));
head=;tail=;level[s]=;q[++tail]=s;
while(++head<=tail){
int x=q[head];
for(int i=linkk[x];i;i=e[i].next){
if(level[e[i].y]==-&&e[i].flow){
q[++tail]=e[i].y;
level[e[i].y]=level[x]+;
}
}
}
return level[t]>;
}
int find(int x,int flow){
if(x==t)return flow;
int maxflow=,d=;
for(int i=linkk[x];i&&maxflow<flow;i=e[i].next){
if(level[e[i].y]==level[x]+&&e[i].flow){
if(d=find(e[i].y,min(flow-maxflow,e[i].flow))){
maxflow+=d;
e[i].flow-=d;
e[e[i].re].flow+=d;
}
}
}
if(!maxflow)level[x]=-;
return maxflow;
}
void work(){
int d=,ans=;
while(bfs())
while(d=find(s,inf))
ans+=d;
cout<<sum-ans<<endl;
}
int main(){
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
init();
work();
}