/*****************************************
备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int to1[N] , head1[N] , ne1[N] ,id1; 
int to2[N] , head2[N] , ne2[N] ,id2;
int a[N] , n , m; 
int dis1[N] , dis2[N],vis[N];
void add1(int x,int y)
{
	to1[++id1] = y;
	ne1[id1] = head1[x];
	head1[x] = id1; 
}
void add2(int x,int y)
{
	to2[++id2] = y;
	ne2[id2] = head2[x];
	head2[x] = id2; 
}
void spfa1()
{
	memset(vis,0,sizeof(vis));
	memset(dis1,0x3f,sizeof(dis1));
	dis1[1] = a[1];
	queue<int> p;
	p.push(1);
	vis[1] = 1;
	while(!p.empty())
	{
		int t = p.front();
		p.pop();
		for(int i = head1[t] ; i ; i = ne1[i])
		{
			int v = to1[i];
			if(min(a[v] ,dis1[t]) < dis1[v])
			{
				dis1[v] = min(dis1[t],a[v]);
				if(!vis[v])
					p.push(v),vis[v] = 1;
			}
		}
	}
}
void spfa2()
{
	memset(vis,0,sizeof(vis));
	memset(dis2,-0x3f,sizeof(dis2));
	queue<int> p;
	p.push(n);
	dis2[n] = a[n];
	vis[n] = 1;
	while(!p.empty())
	{
		int t = p.front();
		p.pop();
		vis[t] = 0;
		for(int i = head2[t] ; i ; i = ne2[i])
		{
			int v = to2[i];
			if(max(dis2[t],a[t]) > dis2[v])
			{
				dis2[v] = max(a[t],dis2[v]);
				if(!vis[v])
					p.push(v),vis[v] = 1;
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for(int i = 1 ; i <= n ;i++)
		scanf("%d",&a[i]);
	int x,y,k;
	while(m--)
	{
		scanf("%d%d%d",&x,&y,&k);
		if(k == 1)
			add1(x,y) , add2(y,x);
		else 
			add1(x,y) , add1(y,x),add2(x,y),add2(y,x);
	}
	spfa1();
	spfa2();
	int maxx = 0;
	for(int i = 1; i <= n ; i++)
		maxx = max(dis2[i] - dis1[i] , maxx);
	cout << maxx << endl;
	return 0;
}