后三个点MLE，其余Ac，求调

#include<bits/stdc++.h>
using namespace std;
struct Side {
	int x, y;
};
int *to, *ne, la[100001], fa[100001], dfn[100001], low[100001], instack[100001], M = 0, Time = 1;
int In[100001], Out[100001], fee = 0, vis[100001];
stack < int > q;
void build(int u, int v) {
	to[++M] = v, ne[M] = la[u], la[u] = M;
	return ;
}
void Tarjan(int x) {
	dfn[x] = Time, low[x] = Time;
	Time++;
	q.push(x);
	instack[x] = 1;
	for (int i = la[x]; i; i = ne[i]) {
		if (!dfn[to[i]]) {
			Tarjan(to[i]);
			low[x] = min(low[x], dfn[to[i]]);
		} else if (instack[to[i]]) {
			low[x] = min(low[x], dfn[to[i]]);
		}
	}
	if (dfn[x] == low[x]) {
		while (q.top() != x) {
			fa[q.top()] = x, In[x] = min(In[x], In[q.top()]), Out[x] = max(Out[x], Out[q.top()]);
			instack[q.top()] = 0, q.pop();
		}
		fa[q.top()] = x;
		instack[q.top()] = 0, q.pop();
	}
	return ;
}
void solve(int Fa, int x) {
	for (int i = la[x]; i; i = ne[i]) {
		if (vis[x] == 0) solve(x, to[i]);
		if (ava[to[i]] == 1) ava[x] = 1;
		Out[x] = max(Out[x], Out[to[i]]);
	}
	vis[x] = 1;
	if (ava[x] == 1) {
		fee = max(fee, Out[x] - In[x]);
	} else {
		Out[x] = 0;
	}
	return ;
}
/*inline void read(int &x) {
	x = 0;
	int f = 1;
	char s = getchar();
	while (s < '0' || s > '9') {
		if (s == '-') f = -1;
		s = getchar();
	}
	while (s >= '0' && s <= '9') {
		x = x * 10 + s - 48;
		s = getchar();
	}
	x *= f;
	return;
}
*/
int main() {
	int n, m;
	cin >> n >> m;
	to=new int[2*m+1],ne=new int[2*m+1];
	Side e[2000001];
	for (int i = 1; i <= n; i++) {
		cin >> In[i];
		Out[i] = In[i];
	}
	memset(la, 0, sizeof(la));
	memset(instack, 0, sizeof(instack));
	for (int i = 1; i <= m;) {
		int kind, X, Y;
		cin >> X >> Y >> kind;
		if (kind == 1) {
			e[i].x = X, e[i].y = Y;
			build(X, Y);
			i++;
		} else {
			build(X, Y);
			build(Y, X);
			m--;
		}
	}//保留有向边，m等于有向边数
	Tarjan(1);
	//memset(to, 0, sizeof(to));
	//memset(ne, 0, sizeof(ne));
	memset(la, 0, sizeof(la));
	M = 0;
	//for(int i=1;i<=n;i++) cout<<fa[i]<<endl;
	for (int i = 1; i <= m; i++) {
		if (fa[e[i].x] != fa[e[i].y]) build(fa[e[i].x], fa[e[i].y]);
	}
	memset(ava, 0, sizeof(ava));
	ava[n] = 1;
	solve(1, 1);
	for (int i = 1; i <= n; i++) {
		//	if(fa[i]==i) cout<<i<<" "<<In[i]<<" "<<Out[i]<<endl;
	}
	cout << fee;
	return 0;
}