#include<bits/stdc++.h>
#include<stack>
#include<cstdio>
using namespace std;
const int N=100005,M=500005,MAXN=1e9;
int n,m,cnt,minx=MAXN,maxx,a[N],head[M];
int time_stamp,tot,totn,minn[N],maxn[N];
int belong[N],dfn[N],low[N];
bool vis[N];
stack<int> s;
struct edge
{
	int v,next;
}es[M];
void addedge(int x,int y)
{
	es[cnt++].v=y;
	es[cnt].next=head[x];
	head[x]=cnt;
}
void Tarjan(int x)
{
	time_stamp++;
	dfn[x]=time_stamp;
	low[x]=time_stamp;
	vis[x]=1;
	s.push(x);
	for(int i=head[x];i>0;i=es[i].next)
	{
		int v=es[i].v;
		if(!dfn[v])
		{
			Tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else if(vis[v])	low[x]=min(low[x],low[v]);
	}
	if(dfn[x]==low[x])
	{
		tot++;
		int tmp;
		while(!s.empty())
		{
			tmp=s.top();
			s.pop();
			vis[tmp]=0;
			belong[tmp]=tot;
			minn[tot]=min(minn[tot],a[tmp]);
			maxn[tot]=max(maxn[tot],a[tmp]);
			if(tmp==n)	totn=tot;
			if(x==tmp)	break;
		}
	}
}
void dfs(int x)
{
	minx=min(minx,minn[belong[x]]);
	maxx=max(maxx,maxn[belong[x]]);
	if(x==n)
	{
		printf("%d",maxx-minx);
		exit(0);
	}
	for(int i=head[x];i>0;i=es[i].next)
	{
		int v=es[i].v;
		if(belong[x]!=belong[v])	dfs(v);
	}
}
int main()
{
	int x,y,z;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		addedge(x,y);
		if(z==2)
			addedge(y,x);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])	Tarjan(i);
	dfs(1);
	return 0;
}