program zuiyoumaoyi;
type point=record
     other,pre:longint
  end;
var p:array[0..500000]of point;
    last:array[1..100000]of longint;
    max,min,cost:array[1..100000]of longint;
    q:array[1..1000000]of longint;
    v:array[1..100000]of boolean;
    n,r:longint;

procedure build(a,b:longint);
begin
  inc(r);
  p[r].other:=b;
  p[r].pre:=last[a];
  last[a]:=r;
end;

procedure init;
var i,m,x,y,z:longint;
begin
  readln(n,m);
  for i:=1 to n do
    begin
      read(cost[i]);
      min[i]:=cost[i];
    end;
  for i:=1 to m do
    begin
      readln(x,y,z);
      build(x,y);
      if z=2 then build(y,x);
    end;
end;

procedure spfa;
var head,tail,i,j,x:longint;
begin
  fillchar(v,sizeof(v),false);
  q[1]:=1;head:=1;tail:=1;v[1]:=true;
  while head<=tail do
    begin
      x:=q[head];
      j:=last[x];
      while j<>0 do
        begin
          i:=p[j].other;
          if (min[i]>min[x])or(max[i]<=max[x]) then
            begin
              if min[i]>min[x] then min[i]:=min[x];
              if max[i]<max[x] then max[i]:=max[x];
              if cost[i]-min[i]>max[i] then max[i]:=cost[i]-min[i];
              if not v[i] then
               begin
                 inc(tail);
                 q[tail]:=i;
                 v[i]:=true;
               end;
            end;
          j:=p[j].pre;
        end;
      v[x]:=false;
      inc(head);
      if head>100000 then exit;
    end;
end;

begin
  init;
  spfa;
  writeln(max[n]);
end.

/**************************************************************
	Problem: 2290
	User: admin
	Language: Pascal
	Result: Wrong Answer
****************************************************************/