#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define se second
const int N = 500005;
int n, m;
int a[N], head[N << 1], cnt;
struct node {
    int to, nxt;
} e[N << 1];
void add(int u, int v) {
    e[cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt++;
}
int head1[N << 1], cnt1, vis[N << 1], dis[N << 1], vis1[N << 1], dis1[N << 1];
struct Node {
    int to, nxt;
} e1[N << 1];
void add1(int u, int v) {
    e1[cnt1].to = v;
    e1[cnt1].nxt = head[u];
    head1[u] = cnt1++;
}
void dij() {
    for (int i = 1; i <= n; i++) dis[i] = 1e9;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    dis[1]=a[1];
    q.push(pii(dis[1], 1));
    while (!q.empty()) {
        int u = q.top().se;
        cout<<u<<endl;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for (int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[v] > min(dis[u],a[v])) {
                dis[v] = min(dis[u],a[v]);
                q.push(pii(dis[v], v));
            }
        }
    }
    return;
}
void dij1() {
    for (int i = 1; i <= n; i++) dis1[i] = 0;
    priority_queue<pii> q1;
    dis1[n]=a[n];
    q1.push(pii(dis1[n], n));
    while (!q1.empty()) {
        int u = q1.top().se;
        q1.pop();
        if(vis1[u])continue;
        vis1[u]=1;
        for (int i = head1[u]; ~i; i = e1[i].nxt) {
            int v = e1[i].to;
            if (dis1[v] < max(dis1[u],a[v])) {
                dis1[v] = max(dis1[u],a[v]);
                q1.push(pii(dis1[v], v));
            }
        }
    }
    return;
}
int main() {
    for (int i = 1; i <= N - 10; i++) {
    	vis[i]=0;
    	vis1[i]=0;
        head[i] = -1;
        e[i].nxt = -1;
        cnt = 0;
        head1[i] = -1;
		e1[i].nxt = -1;
        cnt1 = 0;
    }
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (w == 1)
            add(u, v), add1(v, u);
        else
            add(u, v), add(v, u), add1(u, v), add1(v, u);
    }
    dij();
    dij1();
    cout<<0;
    int u = 0;
    for (int i = 1; i <= n; i++) {
    	//if(vis1[i]&&vis[i])
        u = max(u, dis1[i] - dis[i]);
    }
    cout << u;
    return 0;
}