#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define MAXN 222

 #define inf 1<<30

 struct Edge{

     int v,cap,cost,next;

 }edge[MAXN*MAXN];

 int n,m,vs,vt,NE;

 int head[MAXN];

 void Insert(int u,int v,int cap,int cost)

 {

     edge[NE].v=v;

     edge[NE].cap=cap;

     edge[NE].cost=cost;

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

     head[u]=NE++;

     edge[NE].v=u;

     edge[NE].cap=;

     edge[NE].cost=-cost;

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

     head[v]=NE++;

 }

 bool mark[MAXN];

 int dist[MAXN],pre[MAXN],cur[MAXN];

 bool spfa(int vs,int vt)

 {

     memset(mark,false,sizeof(mark));

     fill(dist,dist+MAXN,-inf);

     dist[vs]=;

     queue<int>que;

     que.push(vs);

     while(!que.empty()){

         int u=que.front();

         que.pop();

         mark[u]=false;

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

             int v=edge[i].v,cost=edge[i].cost;

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

                 dist[v]=dist[u]+cost;

                 pre[v]=u;

                 cur[v]=i;

                 if(!mark[v]){

                     mark[v]=true;

                     que.push(v);

                 }

             }

         }

     }

     return dist[vt]>;

 }

 int MinCostFlow(int vs,int vt)

 {

     int flow=,cost=;

     while(spfa(vs,vt)){

         int aug=inf;

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

             aug=min(aug,edge[cur[u]].cap);

         }

         flow+=aug,cost+=aug*dist[vt];

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

             edge[cur[u]].cap-=aug;

             edge[cur[u]^].cap+=aug;

         }

     }

     return cost;

 }

 int main()

 {

     int x,u,v,cap,cost;

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

         vs=,vt=n+;

         NE=;

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

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

             scanf("%d",&x);

             Insert(i,vt,inf,x);

         }

         while(m--){

             scanf("%d%d%d%d",&u,&v,&cap,&cost);

             Insert(u,v,cap,-cost);

             Insert(v,u,cap,-cost);

         }

         Insert(vs,,inf,);

         printf("%d\n",MinCostFlow(vs,vt));

     }

     return ;

 }