详见BYV的博客，写的非常全面https://www.byvoid.com/blog/noi-2008-employee
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
var
n, m :longint;
pre, other, len, cost :array[..] of longint;
last :array[..] of longint;
l :longint;
source, sink :longint;
ans :longint;
flag :array[..] of boolean;
dis, que, father :array[..] of longint;
function min(a,b:longint):longint;
begin
if a>b then min:=b else min:=a;
end;
procedure connect(a,b,c,d:longint);
begin
inc(l);
pre[l]:=last[a];
last[a]:=l;
other[l]:=b;
len[l]:=c;
cost[l]:=d;
end;
procedure init;
var
i :longint;
x, y, z :longint;
begin
read(n,m);
source:=n+; sink:=source+;
x:=;
l:=;
for i:= to n do
begin
read(y);
if y-x> then
begin
connect(source,i,y-x,);
connect(i,source,,);
end else
begin
connect(i,sink,x-y,);
connect(sink,i,,);
end;
x:=y;
end;
connect(n+,sink,x,);
connect(sink,n+,,);
for i:= to m do
begin
read(x,y,z);
connect(x,y+,maxlongint div ,z);
connect(y+,x,,-z);
end;
for i:= to n+ do
begin
connect(i,i-,maxlongint div ,);
connect(i-,i,,);
end;
end;
function spfa:boolean;
var
h, t, cur :longint;
q, p :longint;
begin
filldword(dis,sizeof(dis) div ,maxlongint div );
que[]:=source;
dis[source]:=;
h:=; t:=;
while t<>h do
begin
h:=h mod +;
cur:=que[h];
flag[cur]:=false;
q:=last[cur];
while q<> do
begin
p:=other[q];
if len[q]> then
if dis[p]>dis[cur]+cost[q] then
begin
father[p]:=q;
dis[p]:=dis[cur]+cost[q];
if not flag[p] then
begin
t:=t mod +;
que[t]:=p;
flag[p]:=true;
end;
end;
q:=pre[q];
end;
end;
if dis[sink]=maxlongint div then exit(false) else exit(true);
end;
procedure update;
var
low, cur :longint;
begin
cur:=sink;
low:=maxlongint;
while cur<>source do
begin
low:=min(low,len[father[cur]]);
cur:=other[father[cur] xor ];
end;
cur:=sink;
while cur<>source do
begin
dec(len[father[cur]],low);
inc(len[father[cur] xor ],low);
ans:=ans+low*cost[father[cur]];
cur:=other[father[cur] xor ];
end;
end;
procedure main;
begin
while spfa do
update;
writeln(ans);
end;
begin
init;
main;
end.