// 用spfa算法去做最值,完全能过
#include<bits/stdc++.h>
using namespace std;

#define ft first
#define se second

typedef pair<int, int> PII;

const int N=1e5+10, M=1e6+10, INF=0x3f3f3f3f;
int h[N], e[M], ne[M], idx;
int mn[N], val[N];
int p[N];
int n, m;
int q[N];
bool st[N];

void add(int a, int b){
    e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}

void spfa_mn(){
    memset(mn, 0x3f, sizeof mn);
    memset(st, 0, sizeof st);
    mn[1]=p[1];

    int hh=0, tt=1;
    q[0]=1, st[1]=true;

    while(hh!=tt){
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;

        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(mn[j]>min(p[j], mn[t])){
                mn[j]=min(p[j], mn[t]);
                if(!st[j]){
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
}

void spfa_val(){
    memset(val, 0, sizeof val);
    memset(st, 0,sizeof st);
    val[1]=0;

    int hh=0, tt=1;
    q[0]=1;
    st[1]=true;

    while(hh!=tt){
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;

        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(val[j]<max(val[t], p[j]-mn[j])){
                val[j]=max(val[t], p[j]-mn[j]);
                if(!st[j]){
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
}

void work(){
    scanf("%d%d", &n, &m);

    for(int i=1;i<=n;i++) scanf("%d", &p[i]);

    memset(h, -1, sizeof h);
    while(m--){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);

        if(z==1) add(x,y);
        else if(z==2) add(x,y), add(y,x);
    }

    spfa_mn();
    spfa_val();

    printf("%d\n", val[n]);
}

int main(){
    work();
    return 0;
}