测试结果2: 通过本测试点|有效耗时156ms
测试结果3: 通过本测试点|有效耗时188ms
测试结果4: 通过本测试点|有效耗时453ms
测试结果5: 通过本测试点|有效耗时437ms
测试结果6: 通过本测试点|有效耗时203ms
测试结果7: 通过本测试点|有效耗时204ms
测试结果8: 通过本测试点|有效耗时312ms
测试结果9: 通过本测试点|有效耗时500ms
测试结果10: 通过本测试点|有效耗时469ms
var x,y:array[0..1000001]of longint;
w,f,d1,d2,q:array[0..100001]of longint;
flag:array[0..100001]of boolean;
n,m,z,e:longint;
function fmin(a,b:longint):longint;
begin if a<b then exit(a);exit(b);end;
function fmax(a,b:longint):longint;
begin if a>b then exit(a);exit(b);end;
procedure swap(var a,b:longint);
var t:longint;
begin t:=a;a:=b;b:=t;end;
procedure qs(l,r:longint);
var i,j,m:longint;
begin
i:=l;j:=r;m:=x[(l+r)div 2];
repeat
while x[i]<m do inc(i);
while x[j]>m do dec(j);
if i<=j then
begin
swap(x[i],x[j]);
swap(y[i],y[j]);
inc(i);dec(j);
end;
until i>j;
if i<r then qs(i,r);
if l<j then qs(l,j);
end;
procedure init;
var i:longint;
begin
readln(n,m);
for i:=1 to n do read(w[i]);
readln;
e:=0;
for i:=1 to m do
begin
inc(e);
readln(x[e],y[e],z);
if z=2 then begin inc(e);x[e]:=y[e-1];y[e]:=x[e-1];end;
end;
end;
procedure spfa1;
var i,h,t,v,u,o,ww:longint;
begin
qs(1,e);
fillchar(f,sizeof(f),0);
for i:=1 to e do
if f[x[i]]=0 then f[x[i]]:=i;
f[n+1]:=e+1;
for i:=n downto 1 do
if f[i]=0 then f[i]:=f[i+1];
for i:=1 to n do d1[i]:=200;
fillchar(flag,sizeof(flag),false);
fillchar(q,sizeof(q),0);
h:=0;t:=1;q[t]:=1;flag[1]:=true;d1[1]:=w[1];o:=0;
while h<>t do
begin
h:=(h mod 100000)+1;
v:=q[h];
flag[v]:=false;
if f[v]<>0 then
for i:=f[v] to f[v+1]-1 do
begin
inc(o);
if o>1000000 then break;
u:=y[i];
ww:=fmin(w[u],d1[v]);
if ww<d1[u] then d1[u]:=ww;
if not flag[u] then
begin
t:=(t mod 100000)+1;
q[t]:=u;
flag[u]:=true;
end;
end;
if o>1000000 then break;
end;
end;
procedure spfa2;
var i,h,t,v,u,o,ww:longint;
begin
for i:=1 to e do
swap(x[i],y[i]);
qs(1,e);
fillchar(f,sizeof(f),0);
for i:=1 to e do
if f[x[i]]=0 then f[x[i]]:=i;
f[n+1]:=e+1;
for i:=n downto 1 do
if f[i]=0 then f[i]:=f[i+1];
fillchar(d2,sizeof(d2),0);
fillchar(flag,sizeof(flag),false);
fillchar(q,sizeof(q),0);
h:=0;t:=1;q[t]:=n;flag[n]:=true;d2[n]:=w[n];o:=0;
while h<>t do
begin
h:=(h mod 100000)+1;
v:=q[h];
flag[v]:=false;
if f[v]<>0 then
for i:=f[v] to f[v+1]-1 do
begin
inc(o);
if o>1000000 then break;
u:=y[i];
ww:=fmax(w[u],d2[v]);
if ww>d2[u] then d2[u]:=ww;
if not flag[u] then
begin
t:=(t mod 100000)+1;
q[t]:=u;
flag[u]:=true;
end;
end;
if o>1000000 then break;
end;
end;
procedure print;
var i,max:longint;
begin
max:=0;
for i:=1 to n do
if (d1[i]<>200)and(d2[i]<>0)and(d2[i]-d1[i]>max) then max:=d2[i]-d1[i];
writeln(max);
end;
begin
init;
spfa1;
spfa2;
print;
end.