Rt

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3fffffff
int n,m,city[100001],x,y,z,ans=-INF;
struct Edge{int from,to,dis;};
Edge pos_edge[500001];
Edge nag_edge[500001];
int pos_head[500001],pos_dis[500001],pos_tot=0,nag_head[500001],nag_dis[500001],nag_tot=0;
bool inq[500001];
void pos_add_edge(int from,int to,int dis)
	{
    	pos_edge[++pos_tot].from=pos_head[from];
    	pos_edge[pos_tot].to=to;
    	pos_edge[pos_tot].dis=dis;
    	pos_head[from]=pos_tot;
	}
void nag_add_edge(int from,int to,int dis)
	{
    	nag_edge[++nag_tot].from=nag_head[from];
    	nag_edge[nag_tot].to=to;
    	nag_edge[nag_tot].dis=dis;
    	nag_head[from]=nag_tot;
	}
void pop_spfa(int s)
	{
		queue<int> q;
    	memset(inq,false,sizeof(inq));
    	q.push(s);
    	inq[s]=true;
    	pos_dis[1]=city[1];
    	for (int i=2;i<=m;i++) pos_dis[i]=INF;
    	while (!q.empty())
			{
        		int u=q.front();
        		q.pop();
        		inq[u]=false;
        		for (int i=pos_head[u];i!=0;i=pos_edge[i].from)
					{
            			int v=pos_edge[i].to;
            			int w=pos_edge[i].dis;
            			if (pos_dis[v]>w||pos_dis[v]<pos_dis[u])
							{
                				pos_dis[v]=min(w,pos_dis[u]);
                				if (!inq[v])
									{
                    					inq[v]=true;
                    					q.push(v);
                					}
            				}
        			}
    		}
	}
void nag_spfa(int s)
	{
		queue<int> q;
    	memset(inq,false,sizeof(inq));
    	q.push(s);
    	inq[s]=true;
    	nag_dis[m]=city[m];    
    	for(int i=1;i<m;i++) nag_dis[i]=-INF;
		while(!q.empty())
			{
        		int u=q.front();
        		q.pop();
        		inq[u]=false;
        		for(int i=nag_head[u];i!=0;i=nag_edge[i].from)
					{
            			int v=nag_edge[i].to;
            			int w=nag_edge[i].dis;
            			if(nag_dis[v]<w||nag_dis[v]<nag_dis[u])
							{
                				nag_dis[v]=max(w,nag_dis[u]);
                				if (!inq[v])
									{
                    					inq[v]=true;
                    					q.push(v);
                					}
            				}
        			}
    		}
	}
int main()
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>city[i];
		for(int i=1;i<=m;i++)
			{
				cin>>x>>y>>z;
				switch(z)
					{
						case 1:
                			pos_add_edge(x,y,city[y]);
                			nag_add_edge(y,x,city[x]);
                			break;
            			case 2:
                			pos_add_edge(x,y,city[y]);
                			nag_add_edge(y,x,city[x]);
                			pos_add_edge(y,x,city[x]);
                			nag_add_edge(x,y,city[y]);
                			break;
					}
			}
		pop_spfa(1);
		nag_spfa(n);
		for (register int i=1;i<=n;i++) ans=max(ans,nag_dis[i]-pos_dis[i]);
		cout<<ans;
	}