//以城市k为分界点
//在走到城市 k 之前(或在城市 k )买入水晶球(可以多次经过城市 k )
//在从城市 k 出发后, 走到城市 n 之前(或在城市 n )卖出水晶球 (可以多次经过城市 n , 最后回到城市 n)
//计算从 1 走到 k , 能够买到水晶球的最低价格
//计算从 k 走到 n , 能够卖出水晶球的最高价格
//则以 k 为分界点所得差旅费就是 max(k~n)-min(1~k)
//关键在于城市之间有双向路,也有单向路,有可能存在环路,所以不能用动态规划计算水晶球的最低最高价格
//可以经过城市 k 买到最便宜的水晶球再回到 k , 也可以经过城市 n 以最贵的价格在另一个城市卖出后再回到城市 n
//所以第一次经过城市 k 的时候,得到的不一定是水晶球的最低(或最高)价格,因此不能用 dijkstra 计算,需要用 spfa
//spfa 时间复杂度是 O(km) k一般很小 最坏情况时 O(nm) n-点数 m-边数
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10, M = 5e5+10;
int n, m;
int h[N], rh[N], e[2*M], ne[2*M], idx;
int maxp[N], minp[N], w[N];
void add(int h[], int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void spfa(int dis[], int h[], int k, int f){
queue<int> q;
bool vis[N] = {false};
//错误 dis 是指针 不能正确反映数组大小
//if(f) memset(dis, 0, sizeof dis);
//else memset(dis, 0x3f, sizeof dis);
if(f) memset(dis, 0, sizeof maxp);
else memset(dis, 0x3f, sizeof minp);
q.push(k);
dis[k] = w[k], vis[k] = false;
while(q.size()){
int t = q.front();
q.pop();
vis[t] = false;
for(int i=h[t]; ~i; i=ne[i]){
int j = e[i];
if(f && dis[j]<max(dis[t], w[j]) || !f && dis[j]>min(dis[t], w[j])){
if(f) dis[j] = max(dis[t], w[j]);
else dis[j] = min(dis[t], w[j]);
if(!vis[j]){
q.push(j);
vis[j] = true;
}
}
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) scanf("%d", &w[i]);
memset(h, -1, sizeof h);
memset(rh, -1, sizeof rh);
int x, y, z;
for(int i=0; i<m; i++){
scanf("%d%d%d", &x, &y, &z);
add(h, x, y), add(rh, y, x);
if(z==2) add(h, y, x), add(rh, x, y);
}
spfa(minp, h, 1, 0); //minp[k] 表示最后到达城市 k 买到的水晶球的最低价格
spfa(maxp, rh, n, 1); //maxp[k] 表示最后到达城市 n 能卖出水晶球的最高价格
int ans = 0;
for(int i=1; i<=n; i++) ans = max(ans, maxp[i]-minp[i]);
cout<< ans<< endl;
return 0;
}