非常棒非常棒的费用流（线性规划）题目，我暂时不会simplex所以只能用费用流水水
//By Richard
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read4.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
template <typename T>
inline void read(T &x,T &y,T &z){read(x);read(y);read(z);}
/////////////////////graph///////////////////////////////
const int MAXV=1111,MAXE=51111;
struct EDGE
{
int u,v,w,cost;
};
struct GRAPH
{
EDGE edge[MAXE];
int next[MAXE],first[MAXV],cnt;
inline void init()
{
cnt=0;
cls(edge);
cls(next);
memset(first,-1,sizeof(first));
}
inline void addedge(int u,int v,int w,int cost)
{
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].cost=cost;
next[cnt]=first[u];
first[u]=cnt++;
edge[cnt].u=v;
edge[cnt].v=u;
edge[cnt].w=0;
edge[cnt].cost=-cost;
next[cnt]=first[v];
first[v]=cnt++;
}
int distance[MAXV],route[MAXV],maxflow;
bool vis[MAXV];
queue <int> qu;
inline bool spfa(int s,int t)
{
memset(distance,0x3f,sizeof(distance));
memset(route,-1,sizeof(route));
cls(vis);
distance[s]=0;
vis[s]=true;
qu.push(s);
while (!qu.empty())
{
int p=qu.front();
qu.pop();
int q=first[p];
vis[p]=false;
while (q!=-1)
{
if (edge[q].w&&distance[edge[q].v]>distance[p]+edge[q].cost)
{
distance[edge[q].v]=distance[p]+edge[q].cost;
route[edge[q].v]=q;
if (!vis[edge[q].v])
{
qu.push(edge[q].v);
vis[edge[q].v]=true;
}
}
q=next[q];
}
}
if (distance[t]==inf) return false;
return true;
}
int MCMF(int s,int t)
{
int mincost=0,nowflow=0,minflow;
while (spfa(s,t))
{
minflow=inf+1;
int q=route[t];
while (q!=-1)
{
minflow=min(minflow,edge[q].w);
q=route[edge[q].u];
}
nowflow+=minflow;
q=route[t];
while (q!=-1)
{
edge[q].w-=minflow;
edge[q^1].w+=minflow;
q=route[edge[q].u];
}
mincost+=distance[t]*minflow;
}
maxflow=nowflow;
return mincost;
}
}graph;
int n,s,t,a[MAXV],m;
int main()
{
read(n,m);
s=0,t=n+2;
graph.init();
rep(i,1,n) read(a[i]);
int x,y,z;
rep(i,1,m)
{
read(x,y,z);
graph.addedge(x,y+1,inf,z);
}
a[0]=a[n+1]=0;
rep(i,1,n+1)
{
int temp=a[i]-a[i-1];
if (temp>=0) graph.addedge(s,i,temp,0);
else graph.addedge(i,t,-temp,0);
}
rep(i,1,n) graph.addedge(i+1,i,inf,0);
printf("%d\n",graph.MCMF(s,t));
return 0;
}