// https://www.luogu.com.cn/problem/P1073

/*
 * 动态规划+最短路径
 * 对于每一个以1为起点的路径：
 * 1. 可以预先求出1到某一结点i路径上水晶球最便宜的价格mn[i]
 * 2. 求1到某一结点i路径上最大利润val[i]时，相对于1到该结点前一个结点i的路径上的最大利润v来说：
 * 更新的可能值只可能是p[i]-mn[i]
 * 所以更新val[i]=max(p[i]-mn[i], max{v})
 * 
 * 值得注意的是，当用求最短路径的方法去求路径上最值的时候，
 * dijkstra不能用判重标记
 * 或者说这里根本就不适合使用dijkstra
*/

#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;
bool st[N];

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

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

    priority_queue<PII, vector<PII>, greater<PII>> heap;

    heap.push({mn[1], 1});

    while(heap.size()){
        auto [price, t]=heap.top();
        heap.pop();

        // if(st[t]) continue;
        // st[t]=true;

        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(mn[j]>min(price, p[j])){
                mn[j]=min(price, p[j]);
                heap.push({mn[j], j});
            }
        }
    } 
}

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

    priority_queue<PII, vector<PII>> heap;
    heap.push({val[1], 1});

    while(heap.size()){
        auto [v, t] = heap.top();
        heap.pop();

        // if(st[t]) continue;
        // st[t]=true;

        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]);
                heap.push({val[j], j});
            }
        }
    }
}

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);
    }

    dijkstra_mn();
    dijkstra_val();

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

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