#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#define N 200000
#define inf 1e15
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
struct reads
{
    int num,data,ed;
};
vector<reads>E[N+1];
vector<int>ES[N+1];
void add(int x,int y,int z,int ed)
{
    E[x].push_back((reads){y,z,ed}),E[y].push_back((reads){x,z,ed});
    return;
}
int n,m,length,X[N+1],Y[N+1],Z[N+1],W[N+1],depth[N+1],delta[N+1],fa[N+1],tfa[N+1],snum[N+1];
long long L,dp[N+1],dst[N+1],dst2[N+1],leng[N+1],leng2[N+1],maxn[N+1],maxn2[N+1],smaxn[N+1],smaxn2[N+1];
bool opt,used[N+1],vis[N+1],vst[N+1];
void dfs(int x)
{
    used[x]=1;
    for (int i=0;i<E[x].size();++i)
	if (!used[E[x][i].num])
	    depth[E[x][i].num]=depth[x]+1,vis[E[x][i].ed]=1,fa[E[x][i].num]=x,tfa[E[x][i].num]=E[x][i].ed,dfs(E[x][i].num);
    return;
}
void dfs2(int x)
{
    bool op;
    if (x<=n)
    {
	for (int i=0;i<ES[x].size();++i)
	{
	    dfs2(ES[x][i]);
	    if (ES[x][i]<=n)
	    {
		if (dp[x]+dp[ES[x][i]]+Z[tfa[ES[x][i]]]>L) opt=0;
		dp[x]=max(dp[x],dp[ES[x][i]]+Z[tfa[ES[x][i]]]);
	    }
	    else
	    {
		if (dp[x]+dp[ES[x][i]]>L) opt=0;
		dp[x]=max(dp[x],dp[ES[x][i]]);
	    }
	}
    }
    else
    {
	for (int i=0;i<ES[x].size();++i) dfs2(ES[x][i]);
        dst[0]=maxn[0]=dp[ES[x][0]],smaxn[0]=leng[0]=0;
	for (int i=1;i<=ES[x].size();++i)
	{
	    leng[i]=leng[i-1]+Z[tfa[ES[x][i-1]]];
	    if (i!=ES[x].size()) dst[i]=max(dst[i-1],dp[ES[x][i]]+leng[i]),smaxn[i]=max(smaxn[i-1],dp[ES[x][i]]+leng[i]+maxn[i]),maxn[i]=max(maxn[i-1],dp[ES[x][i]]-leng[i]);
	    else dst[i]=max(dst[i-1],leng[i]),smaxn[i]=max(smaxn[i-1],leng[i]+maxn[i]),maxn[i]=max(maxn[i-1],-leng[i]);
	}
	dst2[ES[x].size()]=maxn2[ES[x].size()]=smaxn2[ES[x].size()]=leng2[ES[x].size()]=0;
	for (int i=ES[x].size()-1;i>=0;--i) leng2[i]=leng2[i+1]+Z[tfa[ES[x][i]]],dst2[i]=max(dst2[i+1],dp[ES[x][i]]+leng2[i]),smaxn2[i]=max(smaxn2[i+1],dp[ES[x][i]]+leng2[i]+maxn2[i]),maxn2[i]=max(maxn2[i+1],dp[ES[x][i]]-leng2[i]);
	dp[x]=inf,ES[x].push_back(x);
	for (int i=0;i+1<ES[x].size();++i)
	{
	    if (max(dst[i],leng[i]+delta[ES[x][i]]+W[tfa[ES[x][i]]])+max(dst2[i+1],leng2[i+1]+delta[ES[x][i+1]]+W[tfa[ES[x][i]]])+Z[snum[x]]>L) continue;
	    if (leng[i]+delta[ES[x][i]]+W[tfa[ES[x][i]]]+maxn[i]>L||leng2[i+1]+delta[ES[x][i+1]]+W[tfa[ES[x][i]]]+maxn2[i+1]>L) continue;
	    if (smaxn[i]>L||smaxn2[i+1]>L) continue;
	    dp[x]=min(dp[x],max(max(dst[i],leng[i]+delta[ES[x][i]]+W[tfa[ES[x][i]]])+Z[snum[x]],max(dst2[i+1],leng2[i+1]+delta[ES[x][i+1]]+W[tfa[ES[x][i]]])));
	}
	ES[x].pop_back(),op=1;
	if (smaxn[ES[x].size()]>L) op=0;
	if (leng[ES[x].size()]+delta[x]+W[snum[x]]+maxn[ES[x].size()]>L) op=0;
	if (leng2[0]+delta[ES[x][0]]+W[snum[x]]+maxn2[0]>L) op=0;
	if (leng[ES[x].size()]+delta[ES[x][0]]+delta[x]+(W[snum[x]]<<1)>L) op=0;
	if (op) dp[x]=min(dp[x],max(max(leng[ES[x].size()]+maxn[ES[x].size()],(long long)(delta[x]+W[snum[x]])),leng[ES[x].size()]+delta[ES[x][0]]+W[snum[x]]));
    }
    return;
}
bool check(long long x)
{
    for (int i=1;i<=length;++i) dp[i]=0;
    L=x,opt=1,dfs2(1);
    return opt&&dp[1]<=L;
}
int main()
{
    int x,y;
    long long ans=-1;
    length=n=read(),m=read();
    for (int i=1;i<=n;++i) delta[i]=read();
    for (int i=1;i<=m;++i) X[i]=read(),Y[i]=read(),Z[i]=read(),W[i]=read(),add(X[i],Y[i],Z[i],i);
    depth[1]=1,dfs(1);
    for (int i=1;i<=m;++i)
	if (!vis[i])
	{
	    x=X[i],y=Y[i],++length;
	    if (depth[x]<depth[y]) swap(x,y);
	    while (x!=y) ES[length].push_back(x),vst[x]=1,x=fa[x];
	    ES[x].push_back(length),snum[length]=i,x=fa[x];
	}
    for (int i=1;i<=n;++i)
	if (fa[i]&&!vst[i])
	    ES[fa[i]].push_back(i);
    for (int i=log(inf)/log(2);i>=0;--i)
	if (ans+(1ll<<i)<=inf&&!check(ans+(1ll<<i)))
	    ans+=(1ll<<i);
    printf("%lld\n",ans+1);
    return 0;
}