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

int n,m,a[100010];
vector<int> es[100010];

int timestamp;
int dfn[100010],low[100010];
stack<int> stk;
bool vis[100010];

int tot;
int belong[100010];
int maxx[100010];
int minn[100010];

vector<int> v_m[100010];

void tarjan(int x)
{
	timestamp++;
	dfn[x]=timestamp;
	low[x]=timestamp;
	stk.push(x);
	vis[x]=1;
	for(int i=0;i<es[x].size();i++)
	{
		int nx=es[x][i];
		if(!dfn[nx])
		{
			tarjan(nx);
			low[x]=min(low[x],low[nx]);
		}
		else if(vis[nx]) low[x]=min(low[x],low[nx]);
	}
	if(dfn[x]==low[x])
	{
		tot++;
		while(!stk.empty())
		{
			int tmp=stk.top();
			stk.pop();
			vis[tmp]=1;
			belong[tmp]=tot;
			maxx[tot]=max(maxx[tot],a[tmp]);
			minn[tot]=min(minn[tot],a[tmp]);
			if(tmp==x) break;
		}
	}
}

int ans=0;
void dfs(int x,int nmin,int nans)
{
	//printf("(%d,%d,%d)",x,nmin,nans);
	if(x==belong[n])
	{
		ans=max(ans,nans);
		return;
	}
	for(int i=0;i<v_m[x].size();i++)
	{
		int nx=v_m[x][i];
		dfs(nx,min(nmin,minn[nx]),max(nans,maxx[nx]-min(nmin,minn[nx])));
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,t;
		cin>>x>>y>>t;
		es[x].push_back(y);
		if(t==2) es[y].push_back(x);
	}
	memset(minn,0x3f,sizeof(minn));
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<es[i].size();j++)
		{
			int ni=es[i][j];
			if(belong[i]!=belong[ni])
			{
				v_m[belong[i]].push_back(belong[ni]);
			}
		}
	}
	dfs(belong[1],minn[belong[1]],maxx[belong[1]]-minn[belong[1]]);
	cout<<ans;
	return 0;
}

60ac,10wa,30tle