每日一水～～～
#include <cstdio>
#include <cstring>
#include <vector>
#define oo 0x3f3f3f3f
#define N 55010
using namespace std; struct Edge {
int u, v, f;
Edge( int u, int v, int f ):u(u),v(v),f(f){}
}; int n, m, src, dst;
vector<Edge> edge;
vector<int> g[N];
int dep[N], cur[N], qu[N], bg, ed, idc;
int sump; void init() {
for( int i=; i<=n+m+; i++ )
g[i].clear();
edge.clear();
sump = ;
idc = ;
}
void adde( int u, int v, int f ) {
g[u].push_back( edge.size() );
edge.push_back( Edge(u,v,f) );
g[v].push_back( edge.size() );
edge.push_back( Edge(v,u,) );
}
bool bfs() {
memset( dep, , sizeof(dep) );
qu[bg=ed=] = src;
dep[src] = ;
while( bg<=ed ) {
int u=qu[bg++];
for( int t=; t<g[u].size(); t++ ) {
Edge &e = edge[g[u][t]];
if( e.f && !dep[e.v] ) {
dep[e.v] = dep[e.u] + ;
qu[++ed] = e.v;
}
}
}
return dep[dst];
}
int dfs( int u, int a ) {
if( u==dst || a== ) return a;
int remain=a, past=, na;
for( int &t=cur[u]; t<g[u].size(); t++ ) {
Edge &e = edge[g[u][t]];
Edge &ve = edge[g[u][t]^];
if( e.f && dep[e.v]==dep[e.u]+ && (na=dfs(e.v,min(remain,e.f))) ) {
remain -= na;
past += na;
e.f -= na;
ve.f += na;
if( !remain ) break;
}
}
return past;
}
int maxflow() {
int flow = ;
while( bfs() ) {
memset( cur, , sizeof(cur) );
flow += dfs(src,oo);
}
return flow;
}
int main() {
while( scanf( "%d%d", &n, &m )== ) {
init();
src = n+m+;
dst = src+;
for( int i=,c; i<=n; i++ ) {
scanf( "%d", &c );
++idc;
adde( idc, dst, c );
}
for( int i=,u,v,p; i<=m; i++ ) {
scanf( "%d%d%d", &u, &v, &p );
++idc;
sump += p;
adde( src, idc, p );
adde( idc, u, oo );
adde( idc, v, oo );
}
printf( "%d\n", sump-maxflow() );
}
}