#include<bits/stdc++.h>
using namespace std;
#define rd(i,n) for(int i=0;i<n;i++)
#define rp(i,n) for(int i=1;i<=n;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define vt vector
#define pb push_back
#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n,m,a,b,c,d,rv[100005],pre[100005],nxt[100005];
ll f[200005],ok[100005],op[100005],Llen[100005],Rlen[100005];
int nt[300005],hd[100005],cnt,idx;
map<int,int>M[100005];
ll lim;
struct edge{
    int fr,to,len,re;
}e[300005];
inline int addedge(int a,int b,int c,int d){
    nt[++cnt]=hd[a],hd[a]=cnt;
    e[cnt]={a,b,c,d};
    return cnt;
}
vt<int>G[200005];
inline ll solve(int x,int p){
  //  cout<<x<<endl;
    if(x<=n){
        ll mx=0,mx2=0;
        for(auto i:G[x])if(i!=p){
            ll cur=solve(i,x);
            if(cur>mx)mx2=mx,mx=cur;
            else if(cur>mx2)mx2=cur;
        }
        if(mx+mx2>lim)return lim+1;
        return mx;
    }
    vt<int>v;
    for(auto i:G[x])if(i!=p){
        f[i]=solve(i,x);
        if(f[i]>lim)return lim+1;
        v.pb(i);
    }
    int m=v.size();
    pre[0]=nxt[m-1]=p,f[p]=0;
    rep(i,0,m-2)nxt[i]=v[i+1];
    rep(i,1,m-1)pre[i]=v[i-1];
    ll mx=0,cur=0;
    for(int i=0;i<m;i++){
        ok[i]=1;
        cur+=e[M[v[i]][pre[i]]].len,Llen[i]=cur;
        if(cur+f[v[i]]+mx>lim)ok[i]=0,mx=lim+1;
        mx=max(mx,f[v[i]]-cur);
        if(cur+rv[v[i]]+e[M[v[i]][nxt[i]]].re+mx>lim)ok[i]=0;
    }
    mx=0,cur=0;
    for(int i=m-1;i>=0;i--){
        op[i]=1;
        cur+=e[M[v[i]][nxt[i]]].len,Rlen[i]=cur;
        if(cur+f[v[i]]+mx>lim)op[i]=0,mx=lim+1;
        mx=max(mx,f[v[i]]-cur);
        if(cur+rv[v[i]]+e[M[v[i]][pre[i]]].re+mx>lim)op[i]=0;
    }
    ll ans=1e18;
    set<pll>L,R;cur=0;
    // for(int i=0;i<m;i++)cout<<Rlen[i]<<" ";
    // cout<<endl;
    for(int i=m-1;i>=0;i--){
        R.insert({Rlen[i]+f[v[i]],v[i]});
    }
    for(int i=0;i<m;i++){
        if(((i==0)||ok[i-1])&&op[i]){
            ll cur=e[M[v[i]][pre[i]]].re;
            ll d=(i==0?0:Llen[i-1]);
            L.insert({d+cur+rv[pre[i]],0});
            R.insert({Rlen[i]+cur+rv[v[i]],0});
            if(L.rbegin()->first+R.rbegin()->first<=lim){
                ans=min(ans,max(L.rbegin()->first,R.rbegin()->first));
            }
            L.erase({d+cur+rv[pre[i]],0});
            R.erase({Rlen[i]+cur+rv[v[i]],0});
        }
        R.erase({Rlen[i]+f[v[i]],v[i]});
        L.insert({Llen[i]+f[v[i]],v[i]});
    }
    if(ok[m-1]){
        ll cur=e[M[v[m-1]][nxt[m-1]]].re;
        L.insert({Llen[m-1]+cur+rv[v[m-1]],0});
        R.insert({cur+rv[p],0});
        if(L.rbegin()->first+R.rbegin()->first<=lim){
 //           cout<<m<<endl;
            ans=min(ans,max(L.rbegin()->first,R.rbegin()->first));
        }
    }return ans;
}
inline bool check(ll x){
    lim=x;
    return solve(1,0)<=lim;
}
int dfn[100005],low[100005],st[100005],top,ti;
inline void dfs(int x){
    //建立圆方树
    dfn[x]=low[x]=++ti,st[++top]=x;
    for(int i=hd[x];i;i=nt[i]){
        if(!dfn[e[i].to]){
            dfs(e[i].to);
            low[x]=min(low[x],low[e[i].to]);
            if(low[e[i].to]==dfn[x]){
                idx++;
                while(st[top]!=e[i].to){
                    G[st[top]].pb(idx);
                    G[idx].pb(st[top]);
                    top--;
                }G[st[top]].pb(idx);
                G[idx].pb(st[top]);
                top--;
                G[x].pb(idx);
                G[idx].pb(x);
            }
        }else low[x]=min(low[x],dfn[e[i].to]);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    rp(i,n)cin>>rv[i];
    rp(i,m){
        cin>>a>>b>>c>>d;
        M[a][b]=addedge(a,b,c,d);
        M[b][a]=addedge(b,a,c,d);
    }idx=n;
    dfs(1);
  //  cout<<check(22)<<endl;
    ll l=0,r=1e15,mid,ans=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }cout<<ans<<endl;
    return 0;
}
//Rain Rain Rain