$\texttt{QWQ}$

#include<bits/stdc++.h>
using namespace std;

const int N=500005;
vector<int> g1[N], g2[N];
int dp[N][2];
int in[N];
int dfn[N];
int low[N];
int bl[N];
int dfs_clock, n, m, s, t, scc_cnt;
int val[N];
int mx[N];
int mn[N];
int sccno[N];
stack<int> st;

int min(int a, int b, int c)
{
	return min(a, min(b, c));
}

void tarjan(int u)
{
	dfn[u] = low[u] = ++dfs_clock;
	st.push(u);
	
	for(int i = 0; i < g1[u].size(); i++)
	{
		int v = g1[u][i];
		if(!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(!sccno[v])
		{
			low[u] = min(low[u], dfn[v]);
		}
	}
	
	if(low[u] == dfn[u])
	{
		scc_cnt++;
		int x;
		do
		{
			x = st.top();
			st.pop();
			bl[x] = u;
			sccno[x] = scc_cnt;
			mn[u] = min(mx[u],val[x]);
			mx[u] = max(mx[u],val[x]);
		} while(u != x);
	}
}
void bfs()
{
	queue<int> q;
	for(int i = 1; i <= scc_cnt; i++)
	{
		if(!in[i])
		{
			q.push(i);
		}
	}
	dp[s][0] = mn[s];
	dp[s][1] = mx[s] - mn[s];
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		in[u]=-1;
		for(int i = 0; i < g2[u].size(); i++)
		{
			int v = g2[u][i];
			
			dp[v][0] = min(dp[u][0], mn[v], dp[v][0]);
			dp[v][1] = max(dp[v][1], mx[v] - dp[v][0]);
			dp[v][1] = max(dp[v][1], dp[u][1]);
			
			in[v]--;
			if(!in[v])
			{
				q.push(v);
			}
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &val[i]);
	}
	for(int i = 1; i <= m; i++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		g1[x].push_back(y);
		if(z == 2) g1[y].push_back(x);
	}
	for(int i = 1; i <= n; i++)
	{
		dp[i][0] = 1e9;
		dp[i][1] = -1e9;
		if(!dfn[i])
		{
			tarjan(i);
		}
	}
	s = sccno[1];
	t = sccno[n];
	if(s == t)
	{
		printf("%d", mx[s] - mn[s]);
		return 0;
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j < g1[i].size(); j++)
		{
			int v = g1[i][j];
			if(sccno[i] != sccno[v])
			{
				g2[sccno[i]].push_back(sccno[v]);
				in[sccno[v]]++;
			}
		}
	}
	bfs();
	dp[t][1] = max(dp[t][1], 0);
	printf("%d", dp[t][1]);
}