#include<cstdio>

#include<cstring>

using namespace std;

int a[100001][301],aa[100001][301];

int b[100001],c[100001],d[100001];

int line[100001];

int n;

bool v1[100001],v2[100001];

int spfa1(int l,int r)

{

int i;

while(l<=r)

{

l++;

if(c[line[l]]>b[line[l]])

c[line[l]]=b[line[l]];

for(i=1;i<=a[line[l]][0];i++)

{

if(c[line[l]]<c[a[line[l]][i]])

{

c[a[line[l]][i]]=c[line[l]];

if(!v1[a[line[l]][i]])

{

v1[a[line[l]][i]]=true;

r++;

line[r]=a[line[l]][i];

}

}

}

}

return 0;

}

int spfa2(int l,int r)

{

int i;

while(l<=r)

{

l++;

if(d[line[l]]<b[line[l]])

d[line[l]]=b[line[l]];

for(i=1;i<=aa[line[l]][0];i++)

{

if(d[line[l]]>d[aa[line[l]][i]])

{

d[aa[line[l]][i]]=d[line[l]];

if(!v2[aa[line[l]][i]])

{

v2[aa[line[l]][i]]=true;

r++;

line[r]=aa[line[l]][i];

}

}

}

}

return 0;

}

int main()

{

int m;

cin>>n>>m;

int i;

int x,y,z;

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

{

scanf("%d",&b[i]);

c[i]=999999;

d[i]=0;

}

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

{

scanf("%d%d%d",&x,&y,&z);

a[x][0]++;

a[x][a[x][0]]=y;

if(z==2)

{

a[y][0]++;

a[y][a[y][0]]=x;

}

aa[y][0]++;

aa[y][aa[y][0]]=x;

if(z==2)

{

aa[x][0]++;

aa[x][aa[x][0]]=y;

}

}

memset(v1,false,sizeof(v1));

v1[1]=true;

line[1]=1;

spfa1(0,1);

memset(v2,false,sizeof(v2));

memset(line,0,sizeof(line));

v2[n]=true;

line[1]=n;

spfa2(0,1);

int max=0;

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

if(v1[i]&&v2[i]&&d[i]-c[i]>max)

max=d[i]-c[i];

cout<<max<<endl;

return 0;

}