#include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 using namespace std;

 #define INF (1<<30)

 #define MAXN 111

 #define MAXM 111*222

 struct Edge{

     int u,v,cap,cost,next;

 }edge[MAXM];

 int head[MAXN];

 int NV,NE,vs,vt;

 void addEdge(int u,int v,int cap,int cost){

     edge[NE].u=u; edge[NE].v=v; edge[NE].cap=cap; edge[NE].cost=cost;

     edge[NE].next=head[u]; head[u]=NE++;

     edge[NE].u=v; edge[NE].v=u; edge[NE].cap=; edge[NE].cost=-cost;

     edge[NE].next=head[v]; head[v]=NE++;

 }

 bool vis[MAXN];

 int d[MAXN],pre[MAXN];

 bool SPFA(){

     for(int i=;i<NV;++i){

         vis[i]=;

         d[i]=INF;

     }

     vis[vs]=;

     d[vs]=;

     queue<int> que;

     que.push(vs);

     while(!que.empty()){

         int u=que.front(); que.pop();

         for(int i=head[u]; i!=-; i=edge[i].next){

             int v=edge[i].v;

             if(edge[i].cap && d[v]>d[u]+edge[i].cost){

                 d[v]=d[u]+edge[i].cost;

                 pre[v]=i;

                 if(!vis[v]){

                     vis[v]=;

                     que.push(v);

                 }

             }

         }

         vis[u]=;

     }

     return d[vt]!=INF;

 }

 int MCMF(){

     int res=;

     while(SPFA()){

         int flow=INF,cost=;

         for(int u=vt; u!=vs; u=edge[pre[u]].u){

             flow=min(flow,edge[pre[u]].cap);

         }

         for(int u=vt; u!=vs; u=edge[pre[u]].u){

             edge[pre[u]].cap-=flow;

             edge[pre[u]^].cap+=flow;

             cost+=flow*edge[pre[u]].cost;

         }

         if(cost>=) break;

         res+=cost;

     }

     return res;

 }

 int main(){

     int n,m,a,b,c,d;

     while(~scanf("%d%d",&n,&m)){

         vs=; vt=n+; NV=vt+; NE=;

         memset(head,-,sizeof(head));

         for(int i=; i<=n; ++i){

             scanf("%d",&a);

             addEdge(i,vt,INF,-a);

         }

         while(m--){

             scanf("%d%d%d%d",&a,&b,&c,&d);

             addEdge(a,b,c,d);

             addEdge(b,a,c,d);

         }

         printf("%d\n",-MCMF());

     }

     return ;

 }