/*

中国的题目 ——贱买贵卖 0.0

这题wa了好多遍

第一遍看着题 哎呀这不很简单嘛 从起点能到的点都是合法的点

然后统计合法的点里最大最小值 然后printf

也不知道哪里来的自信 就这么交了 然后爆零了

第二遍想了想 恩 刚开始思路有问题 必须先买后卖

买的点要在卖的前面 恩 很有道理

然后数组模拟着统计了一下i之前的最小值和i之后的最大值

并且确保每个点都是合法的

然后 连样例都不对了.....

第三遍 终于找到了问题的关键（好吧我是看到标签里有spfa才想到了）

因为他是图啊 图啊 而且是有向的 而且有双向边

这个嘛 当然还是跑一遍这个图 按照跑的顺序更新最大最小值

所以正反建边 正反分别跑最大最小就ok了

下面是wa的代码

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 500010

using namespace std;

int n,m,num,head[maxn],v[maxn],sm[maxn],bi[maxn];

bool f[maxn];

struct node

{

    int v,pre;

}e[maxn*];

int init()

{

    int x=;char s=getchar();

    while(s<''||s>'')s=getchar();

    while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

    return x;

}

void Add(int from,int to)

{

    num++;

    e[num].v=to;

    e[num].pre=head[from];

    head[from]=num;

}

void Dfs(int s)

{

    for(int i=head[s];i;i=e[i].pre)

      if(f[e[i].v]==)

        {

          f[e[i].v]=;

          Dfs(e[i].v);

        }

}

void Get_sb()

{

    sm[]=maxn;

    for(int i=;i<=n;i++)sm[i]=min(v[i],sm[i-]);

    for(int i=n;i>=;i--)bi[i]=max(v[i],bi[i-]);

}

int main()

{

    n=init();m=init();

    for(int i=;i<=n;i++)

      v[i]=init();

    int x,y,z;

    for(int i=;i<=m;i++)

      {

          x=init();y=init();z=init();

          if(z==)Add(x,y);

          else Add(x,y),Add(y,x);

      }

    f[]=;Dfs();

    Get_sb();

    int minn=0x3f3f3f3f,maxx=;

    for(int i=;i<=n;i++)

      if(f[i])

        {

          minn=min(minn,bi[i]-sm[i]);

          maxx=max(maxx,bi[i]-sm[i]);

        }

    printf("%d\n",maxx-minn);

    return ;

}

/*这是Ac的代码*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define maxn 500010

using namespace std;

int n,m,num,num2,head[maxn],head2[maxn],v[maxn],dx[maxn],dy[maxn],ans;

bool f[maxn];

struct node

{

    int v,pre;

}e[maxn*],e2[maxn*];

int init()

{

    int x=;char s=getchar();

    while(s<''||s>'')s=getchar();

    while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

    return x;

}

void Add(int from,int to)

{

    num++;

    e[num].v=to;

    e[num].pre=head[from];

    head[from]=num;

}

void Add2(int from,int to)

{

    num2++;

    e2[num2].v=to;

    e2[num2].pre=head2[from];

    head2[from]=num2;

}

void SPFA(int s)

{

    memset(dx,/,sizeof(dx));

    f[s]=;dx[s]=v[s];

    queue<int>q;

    q.push(s);

    while(!q.empty())

      {

          int k=q.front();q.pop();

          for(int i=head[k];i;i=e[i].pre)

            {

                dx[e[i].v]=min(dx[e[i].v],min(v[e[i].v],dx[k]));

                if(f[e[i].v]==)

                  {

                      f[e[i].v]=;

                      q.push(e[i].v);

              }

          }

      }

}

void SPFA2(int s)

{

    f[s]=;dy[s]=v[s];

    queue<int>q;

    q.push(s);

    while(!q.empty())

      {

          int k=q.front();q.pop();

          for(int i=head2[k];i;i=e2[i].pre)

            {

                dy[e2[i].v]=max(dy[e2[i].v],max(v[e2[i].v],dy[k]));

                if(f[e2[i].v]==)

                  {

                      f[e2[i].v]=;

                      q.push(e2[i].v);

              }

          }

      }

}

int main()

{

    n=init();m=init();

    for(int i=;i<=n;i++)

      v[i]=init();

    int x,y,z;

    for(int i=;i<=m;i++)

      {

          x=init();y=init();z=init();

          if(z==)Add(x,y),Add2(y,x);

          else Add(x,y),Add(y,x),Add2(x,y),Add2(y,x);

      }

    SPFA();memset(f,,sizeof(f));SPFA2(n);

    int minn=0x3f3f3f3f,maxx=;

    for(int i=;i<=n;i++)

      ans=max(ans,dy[i]-dx[i]);

    printf("%d\n",ans);

    return ;

}