#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const ll MAXN=4e5+10,LIM=1e15,INF=1e18,mod=5170427;

ll n,m,val[MAXN],cur;
vector<int>t[MAXN],e[MAXN];
typedef array<int,2> pr;
typedef vector<int> vec;

ll F(pr v){
	ull x=v[0],y=v[1];
	return (((x<<32) + y) ^ ((y<<32) + x))%mod;
}
struct HB{
	int fst[mod],nxt[MAXN],tot;
	pr key[MAXN];
	int val[MAXN];

	void ins(pr k,int v){
		ll pos=F(k);

		tot++;
		key[tot] = k;
		val[tot] = v;

		nxt[tot] = fst[pos];fst[pos] = tot;
	}
	int qry(pr k){
		ll pos=F(k);
		for(int u=fst[pos];u;u=nxt[u]){
			if(key[u] == k)return val[u];
		}
		return 0;
	}

}fw,fe;
map<pr,ll>tag;

int dfn[MAXN],fa[MAXN],dtot;

void link(int x,int y){
	e[x].push_back(y);
	e[y].push_back(x);
}

void dfs(int u){
	dfn[u] = ++dtot;
	for(auto v:t[u])if(v!=fa[u]){
		if(!dfn[v]){
			fa[v]=u;
			dfs(v);
		}else if(dfn[v] < dfn[u]){
			++cur;

			int x=u;
			while(1){
				link(cur,x);
				if(x!=v){
					tag[{x,fa[x]}] = tag[{fa[x],x}] = 1;
					x=fa[x];
				}else break;
			}
		}
	}
}

void tomin(ll& x,ll y){x=min(x,y);}
void tomax(ll& x,ll y){x=max(x,y);}

ll mid;
ll dp[MAXN];

int r[MAXN];
ll S[MAXN],L,len;
ll pre[MAXN],suf[MAXN];

ll pv1[MAXN],pv2[MAXN],sv1[MAXN],sv2[MAXN];

ll E[MAXN];

void solve_ring(){ //第一个人是u
	assert(len>2);
	ll U=r[1];
	
	r[len+1] = r[1];
	rep(i,1,len)E[i] = fw.qry({r[i],r[i+1]});

	rep(i,2,len)S[i] = S[i-1] + E[i-1];
	L = S[len+1] = S[len] + E[len];
	//

	pre[0] = suf[len+1] = pv1[0] = pv2[0] = sv1[len+1] = sv2[len+1] = suf[len+2] = sv1[len+2] = sv2[len+2] = -INF;

	rep(i,1,len){
		pre[i]=max(pre[i-1],dp[r[i]] + S[i] + pv2[i-1]);

		pv1[i] = max(pv1[i-1],dp[r[i]] + S[i]);
		pv2[i] = max(pv2[i-1],dp[r[i]] - S[i]);
	}
	per(i,len,1){
		suf[i]=max(suf[i+1],dp[r[i]] - S[i] + sv2[i+1]);

		sv1[i] = max(sv1[i+1],dp[r[i]] - S[i]);
		sv2[i] = max(sv2[i+1],dp[r[i]] + S[i]);
	}
	//
	ll ret=INF;
	
	rep(i,1,len){ //断i和i+1的边
		ll ev=fe.qry({r[i],r[i+1]});
		ll w1=val[r[i]] + ev,w2=val[r[i+1]] + ev;

		if(w1+dp[r[i]] > mid || w2+dp[r[i+1]] > mid)continue; 

		tomax(w1,dp[r[i]]),tomax(w2,dp[r[i+1]]);

		ll mx=max(pre[i-1],suf[i+2]);
		tomax(mx,pv1[i-1] + sv1[i+2] + L);
		tomax(mx,w1+S[i]+pv2[i-1]);tomax(mx,w2-S[i+1]+sv2[i+2]);
		tomax(mx,w1+S[i]+sv1[i+2]+L);

		if(i!=len)tomax(mx,w2-S[i+1]+L+pv1[i-1]);
		else{
			rep(j,2,len-1)tomax(mx,w2+S[j]+dp[r[j]]);
		}

		tomax(mx,w1+w2+L-E[i]);

		if(mx>mid)continue;
		ll nv=max(pv1[i-1],sv1[i+2] + L);
		tomax(nv,w1+S[i]);tomax(nv,w2-S[i+1]+L);
		tomin(ret,nv);
	}

	tomax(dp[U],ret);
}

void dfs2(int u,int fa){
	if(u>n){
		for(auto v:e[u])if(v!=fa)dfs2(v,u);
		return;
	}
	dp[u] = 0;

	for(auto v:e[u])if(v!=fa){
		if(v<=n){ //圆圆边
			ll w=fw.qry({u,v});
			if(dp[v] + w + dp[u] > mid)return (void)(dp[u]=INF);
			tomax(dp[u],dp[v]+w);
			continue;
		}
		//圆方边
		vec V1(0),V2(0);
		int flag=0;
		for(auto p:e[v]){
			if(p!=u)dfs2(p,v);
			if(dp[p] > mid)return (void)(dp[u]=INF);
	
			flag |= (p==u);
			if(!flag)V1.push_back(p);
			else V2.push_back(p);
		}
		len=0;
		for(auto p:V2)r[++len]=p;
		for(auto p:V1)r[++len]=p;

		solve_ring();
		if(dp[u] > mid)return (void)(dp[u]=INF);
	}
}

int check(){
	fill(dp+1,dp+1+n,INF);
	dfs2(1,0);

	return dp[1] != INF;
}

int main(){
	ios::sync_with_stdio(false);

	cin>>n>>m;
	rep(i,1,n)cin>>val[i];

	rep(i,1,m){
		int u,v,w,E;
		cin>>u>>v>>w>>E;
		t[u].push_back(v);
		t[v].push_back(u);

		fw.ins({u,v},w);
		fw.ins({v,u},w);

		fe.ins({u,v},E);
		fe.ins({v,u},E);
	}

	cur=n;
	dfs(1);

	rep(i,2,n)if(!tag[{i,fa[i]}])link(i,fa[i]);
	
	ll L=1,R=LIM,ret=-1;

	while(L<=R){
		mid=(L+R)>>1;
		if(check()){
			ret=mid;R=mid-1;
		}else{
			L=mid+1;
		}
	}

	//assert(ret!=-1);
	cout<<ret<<"\n";

    return 0;
}