#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define maxn 100000
#define inf 210000000

std :: queue <int> Q;
std :: vector <int> S[maxn + 10];
std :: vector <int> newS[maxn + 10];
int vmax[maxn + 10], vmin[maxn + 10];
int goin[maxn + 10], hav[maxn + 10];
int nowmin[maxn + 10], nowmax[maxn + 10];

int n, m, v[maxn + 10], x, y, z;

int stac[maxn + 10], h, nowlen; 
int timer, wh[maxn + 10], dfn[maxn + 10], low[maxn + 10], vis[maxn + 10];

inline void dfs(int i) {
	stac[++h] = i;
	dfn[i] = low[i] = ++timer;
	vis[i] = 1;
	for (int now : S[i])
		if (vis[now]) low[i] = std :: min(low[i], low[now]);
		else dfs(now), low[i] = std :: min(low[i], low[now]);
	if (low[i] != dfn[i]) return;
	nowlen++;
	vmin[nowlen] = inf, vmax[nowlen] = -inf;
	while (stac[h] != i) {
		wh[stac[h]] = nowlen;
		vmin[nowlen] = std :: min(vmin[nowlen], v[stac[h]]);
		vmax[nowlen] = std :: max(vmax[nowlen], v[stac[h]]);
		h--;
	}
	vmin[nowlen] = std :: min(vmin[nowlen], v[stac[h]]);
	vmax[nowlen] = std :: max(vmax[nowlen], v[stac[h]]);
	wh[stac[h--]] = nowlen;
	
	return;
}

int main(void) {
    //freopen("in.in", "r", stdin);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    	scanf("%d", v + i), nowmin[i] = inf;
    while (m--) {
    	scanf("%d %d %d", &x, &y, &z);
    	if (z == 1) {
    		S[x].push_back(y);
		} else {
			S[x].push_back(y);
			S[y].push_back(x);
		}
	}
	for (int i = 1; i <= n; i++)
		if (!wh[i]) dfs(i);
	for (int i = 1; i <= n; i++)
		for (int j : S[i])
			if (wh[i] != wh[j])
				newS[wh[i]].push_back(wh[j]), goin[wh[j]]++;
	hav[wh[1]] = 1;
	for (int i = 1; i <= nowlen; i++) {
		if (!goin[i]) Q.push(i);
		nowmin[i] = vmin[i], nowmax[i] = vmax[i] - vmin[i];
	}
	while (!Q.empty()) {
		int now = Q.front(); Q.pop();
		for (int i : newS[now]) {
			hav[i] |= hav[now];
			goin[i]--;
			if (hav[now]) {
				nowmin[i] = std :: min(nowmin[i], nowmin[now]);
				nowmax[i] = std :: max(std :: max(nowmax[i], nowmax[now]), vmax[i] - nowmin[i]);
			}
			if (!goin[i]) Q.push(i);
		}
	}
	
	printf("%d\n", hav[wh[n]] * nowmax[wh[n]]);
    
    return 0;
}

思路就是缩点+dp