#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll I=1e17;
int n,m,fa[201000];
ll rv[201000];
bool vi[201000],v2[200100];
ll p1[210000],p2[200100],p1_[201000],p2_[201000];
struct ed{int v;ll w1,w2,id;};
int U[201000],V[200010],di[201000];ll w1[200100],w2[200100];
vector<ed>g[200100],g2[200100];
int N;
void dfs(int x){
	for(ed t:g[x])if(t.v!=x){
		int v=t.v;
		if(!fa[v])vi[t.id]=1,di[v]=di[x]+1,fa[v]=x,p1[v]=t.w1,p2[v]=t.w2,dfs(v);
	}
}
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);
	for(int i=1;i<=n;i++)scanf("%lld",&rv[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d%lld%lld",&U[i],&V[i],&w1[i],&w2[i]);
		g[U[i]].push_back((ed){V[i],w1[i],w2[i],i});
		g[V[i]].push_back((ed){U[i],w1[i],w2[i],i});
	}
	N=n,fa[1]=1,dfs(1);
	for(int i=1;i<=m;i++)if(!vi[i]){
		int u=U[i],f=V[i];if(di[u]<di[f])swap(u,f);
		N++;
		g2[f].push_back((ed){N,w1[i],w2[i],i});
		while(u!=f)g2[N].push_back((ed){u,p1[u],p2[u],i}),v2[u]=1,u=fa[u];
	}
	for(int i=2;i<=n;i++)if(!v2[i])g2[fa[i]].push_back((ed){i,p1[i],p2[i],i});
	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;
}