var best,sq,c,w,next,ks,hq:array[1..10000]of longint;
db,db2:array[1..1000,1..10001]of longint;
cz:array[1..10000,1..2]of longint;
dr1,dr2:array[1..10000]of longint;
q1,q2,q3,b,d1,d2,d3,d4,i,j,n,m,k,o,p,min:longint;
b1,b2:array[1..10000]of longint;
function spfa:boolean;
var s,t,zd,zb:longint;
d:array[1..10000]of longint;
v:array[1..10000]of boolean;
begin
s:=0;
t:=1;
d[1]:=1;
for i:=1 to n do begin best[i]:=maxlongint;v[i]:=false;end;
best[1]:=0;
v[1]:=true; fillchar(hq,sizeof(hq),0);
while s<t do
begin
inc(s);
zd:=d[s];
zb:=ks[zd];
repeat
if zb=0 then break;
if (best[b2[zb]]>best[zd]+c[zb])and(w[zb]>0) then
begin
best[b2[zb]]:=best[zd]+c[zb];
hq[b2[zb]]:=zb;
if v[b2[zb]]=false then
begin
inc(t);
d[t]:=b2[zb];
v[b2[zb]]:=true;
end;
end;
if next[zb]=o then break;
zb:=next[zb];
until false;
v[d[s]]:=false;
end;
if best[n]=maxlongint then exit(false) else exit(true);
end;
procedure add;
var zx,i,j:longint;
begin
zx:=maxlongint;
i:=n;
while hq[i]<>0 do
begin
if w[hq[i]]<zx then zx:=w[hq[i]];
i:=b1[hq[i]];
end;
min:=min+zx*best[n];
i:=n;
while hq[i]<>0 do
begin
w[hq[i]]:=w[hq[i]]-zx;
w[sq[hq[i]]]:=w[sq[hq[i]]]+zx;
i:=b1[hq[i]];
end;
end;
procedure build(d1,d2,d3,d4:longint);
begin
inc(b);
b1[b]:=d1;
b2[b]:=d2;
w[b]:=d3;
c[b]:=d4;
sq[b]:=b+1;
if ks[d1]=0 then ks[d1]:=b else
begin
o:=ks[d1];
while next[o]<>0 do o:=next[o];
next[o]:=b;
end;
inc(b);
b1[b]:=d2;
b2[b]:=d1;
w[b]:=0;
c[b]:=-d4;
sq[b]:=b-1;
if ks[d2]=0 then ks[d2]:=b else
begin
o:=ks[d2];
while next[o]<>0 do o:=next[o];
next[o]:=b;
end;
end;
begin
assign(input,'1.txt');
reset(input);
readln(n,m);
for i:=1 to n do
begin
read(dr1[i]);
db[i,m+1]:=dr1[i];
end;
inc(n);
for i:=1 to m do
begin
readln(q1,q2,dr2[i]);
for j:=q1 to q2 do
db[j,i]:=1;
end;
db2:=db;
for i:=1 to m do if db[1,i]=1 then cz[i,1]:=1;
for i:=2 to n do
begin
for j:=1 to m do
begin
db2[i,j]:=db[i,j]-db[i-1,j];
if db2[i,j]=1 then cz[j,1]:=i;
if db2[i,j]=-1 then cz[j,2]:=i;
end;
db2[i,m+1]:=db[i,m+1]-db[i-1,m+1];
end;
db:=db2;
for i:=1 to n do
begin
if db[i,m+1]>=0 then
build(1,1+i,db[i,m+1],0) else build(1+i,n+2,-db[i,m+1],0);
if i<>n then build(i+2,i+1,10000000,0);
end;
for i:=1 to m do
begin
build(cz[i,1]+1,cz[i,2]+1,10000000,dr2[i]);
end;
n:=n+2;
while spfa do add;
writeln(min);
close(input);
end.