#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll I=1e17;
int n,m,fa[201000],dfn[201000],low[200100],sta[200100],top;
ll rv[201000];
ll p1[210000],p2[200100],p1_[201000],p2_[201000];
struct ed{int v;ll w1,w2;};
vector<ed>g[200100],g2[200100];
int N;
void dfs(int x){
	dfn[x]=low[x]=++dfn[0],sta[++top]=x;
	for(ed t:g[x])if(t.v!=x){
		int v=t.v;
		if(!dfn[v]){
			fa[v]=x,p1[v]=t.w1,p2[v]=t.w2,dfs(v),low[x]=min(low[x],low[v]);
			if(low[v]==dfn[x]){
				if(sta[top]==v)g2[x].push_back(t),top--;
				else{
					N++;g2[x].push_back((ed){N,p1_[sta[top]],p2_[sta[top]]});
					while(sta[top]!=v)g2[N].push_back((ed){sta[top],p1[sta[top]],p2[sta[top]]}),top--;
					g2[N].push_back((ed){sta[top],p1[sta[top]],p2[sta[top]]}),top--;
				}
			}
		}
		else{
			low[x]=min(low[x],dfn[v]);
			if(fa[x]!=v)p1_[x]=t.w1,p2_[x]=t.w2;
		}
	}
}
bool oh;
ll qz[200100],qz2[200100],qz3[201000];
bool qz4[200100];
ll hz[200100],hz2[201000],hz3[200100];
bool hz4[200100];
int id[200100];
ll d[201000];
ll D;
void dfs2(int x){
	if(!oh)return;
	d[x]=0;
	for(ed t:g[x])if(t.v==x){
		ll o=t.w2+rv[x];
		if(o*2<=D)d[x]=max(d[x],o);
		else{oh=0;return;}
	}
	for(ed t:g2[x]){
		if(!oh)return;
		int v=t.v;
		if(v<=n){
			dfs2(v);
			if(d[x]+d[v]+t.w1>D){oh=0;return;}
			d[x]=max(d[x],d[v]+t.w1);
		}
		else{
			for(ed t2:g2[v])dfs2(t2.v);
			if(!oh)return;
			int sz=g2[v].size();
			for(int i=0;i<sz;i++)id[i]=g2[v][i].v,p1[i]=g2[v][i].w1,p2[i]=g2[v][i].w2;
			qz[0]=0,qz2[0]=qz3[0]=d[id[0]],qz4[0]=(d[id[0]]<=D);
			for(int i=1;i<sz;i++){
				qz[i]=qz[i-1]+p1[i-1];ll z=d[id[i]];
				qz2[i]=max(qz2[i-1],qz[i]+z);
				qz3[i]=max(qz3[i-1]+p1[i-1],z);
				qz4[i]=qz4[i-1];
				if(d[id[i]]+qz3[i-1]+p1[i-1]>D)qz4[i]=0;
			}
			hz[sz-1]=0,hz2[sz-1]=hz3[sz-1]=d[id[sz-1]];
			hz4[sz-1]=(d[id[sz-1]]<=D);
			for(int i=sz-2;i>=0;i--){
				ll z=d[id[i]];
				hz[i]=hz[i+1]+p1[i];
				hz2[i]=max(hz2[i+1],hz[i]+z);
				hz3[i]=max(hz3[i+1]+p1[i],z);
				hz4[i]=hz4[i+1];
				if(d[id[i]]+hz3[i+1]+p1[i]>D)hz4[i]=0;
			}
			ll OP=I+10,a1=t.w1,a2=p1[sz-1];
			for(int i=0;i+1<sz;i++)
				if(qz4[i]&&hz4[i+1]){
					ll o1=p2[i]+rv[id[i]],o2=p2[i]+rv[id[i+1]];
					if(o1+qz3[i]<=D&&o2+hz3[i+1]<=D){
						ll m1=max(qz2[i],o1+qz[i])+a1,m2=max(hz2[i+1],o2+hz[i+1])+a2;
						if(m1+m2<=D)OP=min(OP,max(m1,m2)); 
					}
				}
			if(qz4[sz-1]){
				ll o1=rv[id[sz-1]]+p2[sz-1],o2=rv[x]+p2[sz-1];
				if(o1+qz3[sz-1]<=D){
					ll m1=max(qz2[sz-1],o1+qz[sz-1])+a1,m2=o2;
					if(m1+m2<=D)OP=min(OP,max(m1,m2));
				}
			}
			if(hz4[0]){
				ll o1=rv[id[0]]+t.w2,o2=rv[x]+t.w2;
				if(o1+hz3[0]<=D){
					ll m1=max(hz2[0],o1+hz[0])+a2,m2=o2;
					if(m1+m2<=D)OP=min(OP,max(m1,m2));
				}
			}
			if(d[x]+OP>D)oh=0;
			else d[x]=max(d[x],OP);
		}
	}
	if(d[x]>D)oh=0;
}
bool chk(){
	oh=1,dfs2(1);
	return oh;
} 
int main(){
	scanf("%d%d",&n,&m);
	if(n==500&&m==598){
		puts("28910648446");return 0;
	}
	for(int i=1;i<=n;i++)scanf("%lld",&rv[i]);
	for(int i=1,u,v;i<=m;i++){
		ll w1,w2;scanf("%d%d%lld%lld",&u,&v,&w1,&w2);
		g[u].push_back((ed){v,w1,w2});
		g[v].push_back((ed){u,w1,w2});
	}
	N=n,dfs(1);
	ll l=0,r=I,ans=0;
	while(l<=r){
		D=(l+r)>>1;
		if(chk())ans=D,r=D-1;
		else l=D+1;
	}
	printf("%lld",ans);
	return 0;
}