rt.首回者有关注

/**
* By @xusiyuan
* In YUANSHIREN
* C++
**/

# include <bits/stdc++.h>
# define N 100005
# define M 10 * N
# define INF 0x3f3f3f3f

using namespace std;

int head[N], rhead[N], ver[M], Next[M], n, m, tot;
int key[N], big[N], small[N], vis[N];
queue <int> Q;

void ADD(int head[], int x, int y) {
	ver[++tot] = y;
	Next[tot] = head[x];
	head[x] = tot;
} 

void SPFAsmall(int root) {
	memset(small, 0x3f, sizeof(small));
	memset(vis, 0, sizeof(vis));
	small[root] = key[root];
	Q.push(root);
	vis[root] = 1;
	while(Q.size()) {
		int x = Q.front();
		Q.pop();
		vis[x] = 0;
		for(int i = head[x]; ~i; i = Next[i]) {
			int y = ver[i];
			if(small[y] > min(small[x], key[y])) {
				small[y] = min(small[x], key[y]);
				if(!vis[y]) {
					Q.push(y);
					vis[y] = 1;
				}
			}
		}
	}
} 

void SPFAbig(int root) {
	memset(big, 0, sizeof(small));
	memset(vis, 0, sizeof(vis));
	big[root] = key[root];
	Q.push(root);
	vis[root] = 1;
	while(Q.size()) {
		int x = Q.front();
		Q.pop();
		vis[x] = 0;
		for(int i = head[x]; ~i; i = Next[i]) {
			int y = ver[i];
			if(big[y] < min(big[x], key[y])) {
				big[y] = min(big[x], key[y]);
				if(!vis[y]) {
					Q.push(y);
					vis[y] = 1;
				}
			}
		}
	}
} 

int main () {

	int x, y, z;
	memset(head, -1, sizeof(head));
	memset(rhead, -1, sizeof(rhead));
	tot = -1;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> key[i];
	for(int i = 1; i <= m; i++) {
		cin >> x >> y >> z;
		ADD(head, x, y);
		ADD(rhead, y, x);
		if(z == 2) {
			ADD(head, y, x);
			ADD(rhead, x, y);
		}
	}
	SPFAsmall(1);
	SPFAbig(n);
	int ans = 0;
	for(int i = 1; i <= n; i++) ans = max(big[i] - small[i], ans);
	cout << ans << "\n";

	return 0;
}