#include<bits/stdc++.h>
using namespace std;
int n,m;
int g[100005];
struct oppo{
    int to,nex;
}rod[1000005];
int head[100005],tot,ans;
void add(int from,int to)
{
    rod[++tot].to=to;
    rod[tot].nex=head[from];
    head[from]=tot;
}
int f[100005];
int MAX[100005];
void dfs(int x,int k,int now)
{
    if(k>=f[x]&&now<=MAX[x]) return;
    f[x]=k;
    MAX[x]=now;
    if(x==n)
        ans=max(ans,now);
    for(int i=head[x];i;i=rod[i].nex){
        int to=rod[i].to;
        dfs(to,min(k,g[to]),max(MAX[x],g[to]-k));
    }
}
int main()
{
    memset(f,10,sizeof(f));
    memset(MAX,-1,sizeof(MAX));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&g[i]);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b);
        if(c==2)
        add(b,a);
    }
    dfs(1,g[1],0);
    cout<<ans<<"\n";
    return 0;
}