program trade;

const maxn=100000;

maxe=1000000;

type ss=record

x,next:longint;

end;

var min,max,a,p,pp,c:array[1..maxn] of longint;

mark:array[1..maxn] of boolean;

e,ee:array[1..maxe] of ss;

total,i,n,m,ans,aa,b,cc:longint;

procedure spfa;

var f,l,t,tmp:longint;

begin f:=0;l:=1;

c[1]:=1;

for i:=1 to n do mark[i]:=true;

for i:=1 to n do min[i]:=1000;

min[1]:=a[1];

repeat

f:=f mod n+1;

mark[c[f]]:=true;

t:=p[c[f]];

while t<>-1 do

begin

if a[e[t].x]<min[c[f]] then tmp:=a[e[t].x]

else tmp:=min[c[f]];

if tmp<min[e[t].x] then begin

min[e[t].x]:=tmp;

if mark[e[t].x] then begin l:=l mod n+1;

c[l]:=e[t].x;

mark[e[t].x]:=false;

end;

end;

t:=e[t].next;

end;

until f=l;

end;

procedure spfa1;

var f,l,t,tmp:longint;

begin f:=0;l:=1;

c[1]:=n;

for i:=1 to n do mark[i]:=true;

for i:=1 to n do max[i]:=0;

max[n]:=a[n];

repeat

f:=f mod n+1;

mark[c[f]]:=true;

t:=pp[c[f]];

while t<>-1 do

begin

if a[ee[t].x]>max[c[f]] then tmp:=a[ee[t].x]

else tmp:=max[c[f]];

if tmp>max[ee[t].x] then begin

max[ee[t].x]:=tmp;

if mark[ee[t].x] then begin l:=l mod n+1;

c[l]:=ee[t].x;

mark[ee[t].x]:=false;

end;

end;

t:=ee[t].next;

end;

until f=l;

end;

begin

assign(input,'trade.in');

assign(output,'trade.out');

reset(input);

rewrite(output);

readln(n,m);

for i:=1 to n do

begin read(a[i]);p[i]:=-1;pp[i]:=-1;end;

readln;

total:=0;

for i:=1 to m do

begin

readln(aa,b,cc);

if cc=1 then begin inc(total);

e[total].x:=b;

e[total].next:=p[aa];

p[aa]:=total;

ee[total].x:=aa;

ee[total].next:=pp[b];

pp[b]:=total;

end

else begin inc(total);

e[total].x:=b;

e[total].next:=p[aa];

p[aa]:=total;

ee[total].x:=b;

ee[total].next:=pp[aa];

pp[aa]:=total;

inc(total);

e[total].x:=aa;

e[total].next:=p[b];

p[b]:=total;

ee[total].x:=aa;

ee[total].next:=pp[b];

pp[b]:=total;

end;

end;

spfa;

spfa1;

ans:=0;

for i:=1 to n do

if max[i]-min[i]>ans then begin ans:=max[i]-min[i];end;

writeln(ans);

end.