The method comes from this big guy

LuoGu Title gate

[Abstract]

There is a very ingenious way to solve this problem: layered graph + SPFA

It can be seen from the question meaning that the output answer is only related to the buying and selling price, and the buying and selling are limited to one time

It's very difficult for us to maintain the status of buying and selling if it's general broad search, and it's also difficult to update the answer

This method is very convenient

Let's build a three-tier diagram

- First floor: initial road, can walk around without weight
- Layer 2: you can walk up and down the same floor as the first floor, but it comes from the first floor. A road is built from the first floor to the second floor, indicating purchase. The weight is - price
- Layer 3: you can walk up and down the same layer as the first layer, but it comes from the second layer. A road is built from the second layer to the third layer, which means selling. The weight is the price

And the end point is n in the third layer. The final result can be compared with 0

This method has a small code size and is very beautiful

Code:

```
uses math;
var
q,dis,dist,next,u,head,w:array[0..1000000] of longint;
vis:array[0..1000000] of boolean;
n,m,x,y,z,i,h,tail,e,ans,num:longint;
procedure add(x,y,z:longint);
begin
inc(num);
u[num]:=y;
dist[num]:=z;
next[num]:=head[x];
head[x]:=num;
end;
begin
readln(n,m);
for i:=1 to n do read(w[i]);
for i:=1 to m do
begin
readln(x,y,z);
add(x,y,0);
add(x+n,y+n,0);
add(x+n+n,y+n+n,0);
add(x,y+n,-w[y]);
add(x+n,y+n+n,w[y]);
if z=2 then
begin
add(y,x,0);
add(y+n,x+n,0);
add(y+n+n,x+n+n,0);
add(y,x+n,-w[x]);
add(y+n,x+n+n,w[x]);
end;
end;
q[1]:=1;
tail:=1;
for i:=2 to 3*n do dis[i]:=-maxlongint;
while h<tail do
begin
inc(h);
x:=q[h];
vis[x]:=false;
i:=head[x];
while i>0 do
begin
e:=u[i];
if (dis[e]<dis[x]+dist[i]) then
begin
dis[e]:=dis[x]+dist[i];
if not vis[e] then
begin
inc(tail);
q[tail]:=e;
vis[e]:=true;
end;
if e=3*n then ans:=max(ans,dis[e]);
end;
i:=next[i];
end;
end;
writeln(ans);
end.
```