#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>

using namespace std;

int n,m,node[100010],dismi[100010],disma[100010],inq[100010],minn,maxn;
vector<int>e[100010];
vector<int>e1[100010];

void spfa(int pos,int f)
{
	if(f==1)
	{
		for(int i=1;i<=n;i++) dismi[i]=1e9;//最小值 
	}
	else//最大值 
	{
		for(int i=1;i<=n;i++)
		{
			disma[i]=-1e9;
			inq[i]=0;
		}
	}
	queue<int>qu;
	inq[pos]=1;
	qu.push(pos);
	dismi[pos]=disma[pos]=node[pos];
	while(!qu.empty())
	{
		int u=qu.front();
		inq[u]=0;
		qu.pop();
		if(f==1)
		{
			for(int i=0;i<e[u].size();i++)
			{
			    int v=e[u][i];
				if(dismi[u]<dismi[v])//玄学的判断 不能写反。。 
				{
					dismi[v]=dismi[u];
					if(inq[v]==0)//是否可更新
					{
						qu.push(v);
						inq[v]=1;
					}
					if(node[v]<dismi[v]) 
					{
						dismi[v]=node[v];	
					}
				}
			}		
		}
		else
		{
			for(int i=0;i<e1[u].size();i++)
			{
			    int v=e1[u][i];
				if(disma[u]>disma[v])//玄学的判断 
				{
					disma[v]=disma[u];
					if(inq[v]==0)
					{
						qu.push(v);
						inq[v]=1;
					}
					if(node[v]>disma[v])
					{
						disma[v]=node[v];
						
			    	}
				}
			}
		}
	}
}

int main()
{
	freopen("trade.in","r",stdin);
	freopen("trade.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&node[i]);
	}
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(c==2)
		{
			e[a].push_back(b);
			e[b].push_back(a);
			e1[a].push_back(b);
			e1[b].push_back(a);
		}
		else
		{
			e[a].push_back(b);
			e1[b].push_back(a);
		}
	}
	spfa(1,1);
	spfa(n,0);//极其精妙的一步保证最大值和最小值连通 
	int s=0;
	for(int i=1;i<=n;i++)
	{
		s=max(disma[i]-dismi[i],s);
	}
	printf("%d",s);
	return 0;
}