#include <iostream>#include <cstdlib>#include <cstdio>#include <string>#include <cstring>#include <algorithm>#include <vector>#include <cmath>#include <queue>#define inf 1111111111using namespace std;struct edges{ int c,f,u,v,to,next;}e[8100];int h[105];int b[105];int pre[105];int vis[105];int ans;int n,m,T=103,k;void link(int v,int u,int c,int f){ e[++k].u=u; e[k].v=v; e[k].c=c; e[k].f=f; e[k].to=k+1; e[k].next=h[v]; h[v]=k; e[++k].v=u; e[k].u=v; e[k].c=0; e[k].to=k-1; e[k].f=-f; e[k].next=h[u]; h[u]=k;}queue<int> s;int spaf(){ int t,i,v,u; for(i=2;i<=T;i++){b[i]=-inf;vis[i]=0;} s.push(1); b[1]=0; vis[1]=1; while(!s.empty()) { v=s.front(); s.pop(); t=h[v]; vis[v]=0; while(t!=-1) { u=e[t].u; if(e[t].c>0&&b[u]<b[v]+e[t].f) { b[u]=b[v]+e[t].f; pre[u]=t; if(!vis[u]) { vis[u]=1; s.push(u); } } t=e[t].next; } } return b[T]>0;}void bfs(){ int v,u,t,flow; int ans=0; while(spaf()) { flow=1<<30; u=T; while(1) { t=pre[u]; if(flow>e[t].c)flow=e[t].c; v=e[t].v; if(v==1)break; u=v; } ans+=b[T]*flow; u=T; while(1) { t=pre[u]; e[t].c-=flow; e[e[t].to].c+=flow; v=e[t].v; if(v==1)break; u=v; } } printf("%dn",ans);}int main(){ int i,c,f,v,u; while(scanf("%d%d",&n,&m)!=EOF) { k=0; memset(h,-1,sizeof(h)); for(i=2;i<=n;i++) { scanf("%d",&f); link(i,T,1<<30,f); } for(i=1;i<=m;i++) { scanf("%d%d%d%d",&v,&u,&c,&f); link(v,u,c,-f); link(u,v,c,-f); } bfs(); } return 0;}
