node=record
x,y,z:longint;
end;
var
i,j,k,l,n,m,ans,r:longint;
e:array [0..200000] of node;
f:array [0..50050] of boolean;
t,p,head:array [0..50500] of longint;
que,min,cost,next:array [0..200000] of longint;
begin
readln(n,m);
ans:=0;
for i:=1 to n do begin
read(p[i]);
min[i]:=p[i];
end;
min[1]:=maxlongint;
p[n]:=-maxlongint;
for i:=1 to m do
with e[i] do begin
read(x,y,z);
next[i]:=head[x];
head[x]:=i;
if z=2 then begin
e[i+m].x:=y;
e[i+m].y:=x;
next[i+m]:=head[y];
head[y]:=i+m;
end;
end;
fillchar(f,sizeof(f),false);
fillchar(cost,sizeof(cost),0);
l:=1; r:=1;
f[1]:=true;
k:=head[1];
while k<>0 do begin
with e[k] do begin
que[r]:=y;
inc(r);
f[y]:=true;
end;
k:=next[k];
end;
while l<>r do begin
k:=head[que[l]];
while k<>0 do begin
with e[k] do begin
if min[y]>min[x] then begin
min[y]:=min[x];
if not f[y] then begin
f[y]:=true;
que[r]:=y;
r:=r mod n+1;
end;
end;
if cost[y]<p[y]-min[y] then cost[y]:=p[y]-min[y];
if cost[y]<cost[x] then begin
cost[y]:=cost[x];
if not f[y] then begin
f[y]:=true;
que[r]:=y;
r:=r mod n+1;
end;
end;
end;
k:=next[k];
end;
f[que[l]]:=false;
l:=l mod n+1;
end;
writeln(cost[n]);
end.