//李老师保佑我AC
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int prime[500005];
int buy[500005],sell[500005];
int last_buy[500005],next_buy[500005],endd_buy[500005],len_buy[500005];
bool flag_buy[500005];
int last_sell[500005],next_sell[500005],endd_sell[500005],len_sell[50005];
bool flag_sell[500005];
int money[500005];
struct yyc_buy
{
	int u;
	int dis;
	yyc_buy(int u_,int dis_)
	{
		u=u_;
		dis=dis_;
	}
};
bool operator < (yyc_buy a,yyc_buy b)
{
	return a.dis>b.dis;
}
priority_queue<yyc_buy> q_buy;
struct yyc_sell
{
	int u;
	int dis;
	yyc_sell(int u_,int dis_)
	{
		u=u_;
		dis=dis_;
	}
};
bool operator < (yyc_sell a,yyc_sell b)
{
	return a.dis<b.dis;
}
priority_queue<yyc_sell> q_sell;
int cnt=0;
void add_buy(int x,int y,int z)
{
	cnt++;
	endd_buy[cnt]=y;
	len_buy[cnt]=z;
	next_buy[cnt]=last_buy[x];
	last_buy[x]=cnt;
}
int num=0;
void add_sell(int x,int y,int z)
{
	num++;
	endd_sell[num]=y;
	len_sell[num]=z;
	next_sell[num]=last_sell[x];
	last_sell[x]=num;
}
void spfa_buy()
{
	while(!q_buy.empty())
	{
		int u=q_buy.top().u;
		q_buy.pop();
		if(flag_buy[u])
		{
			continue;
		}
		flag_buy[u]=1;
		for(int i=last_buy[u];i;i=next_buy[i])
		{
			int v=endd_buy[i];
			if(buy[v]>buy[u]||buy[v]>prime[v])
			{
				buy[v]=min(buy[u],prime[v]);
				q_buy.push(yyc_buy(v,buy[v]));
			}
		}
	}
}
void spfa_sell()
{
	while(!q_sell.empty())
	{
		int u=q_sell.top().u;
		q_sell.pop();
		if(flag_sell[u])
		{
			continue;
		}
		flag_sell[u]=1;
		for(int i=last_sell[u];i;i=next_sell[i])
		{
			int v=endd_sell[i];
			if(sell[v]<sell[u]||sell[v]<prime[v])
			{
				sell[v]=max(sell[u],prime[v]);
				q_sell.push(yyc_sell(v,sell[v]));
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>prime[i];
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		if(z==1)
		{
			add_buy(x,y,1);
			add_sell(y,x,1);
		}
		else
		{
			add_buy(x,y,1);
			add_buy(y,x,1);
			add_sell(x,y,1);
			add_sell(y,x,1);
		}
	}
	for(int i=1;i<=n;i++)
	{
		buy[i]=1e18;
	}
	buy[1]=prime[1];
	q_buy.push(yyc_buy(1,0));
	sell[n]=prime[n];
	q_sell.push(yyc_sell(n,0));
	spfa_buy();
	spfa_sell();
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,sell[i]-buy[i]);
	}
	cout<<ans;
	return 0;
}

用的是dij 大佬帮忙调调吧