#include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int INF=<<;

 int inline readint(){

     int Num;char ch;

     while((ch=getchar())<''||ch>'');Num=ch-'';

     while((ch=getchar())>=''&&ch<='') Num=Num*+ch-'';

     return Num;

 }

 int n,m;

 int A[];

 int S,T;

 int to[],ne[],w[],c[],fir[],cnt=;

 void add(int a,int b,int x,int y=INF){

     to[cnt]=b,w[cnt]=x,c[cnt]=y,ne[cnt]=fir[a],fir[a]=cnt++;

     to[cnt]=a,w[cnt]=-x,c[cnt]=,ne[cnt]=fir[b],fir[b]=cnt++;

 }

 int dis[],pre[];

 bool in[];

 queue <int> q;

 bool Spfa(){

     memset(dis,/,sizeof(dis));

     q.push(S);

     in[S]=true;

     dis[S]=;

     int u;

     while(!q.empty()){

         u=q.front();

         q.pop();

         in[u]=false;

         for(int i=fir[u];i!=-;i=ne[i]){

             int v=to[i];

             if(dis[v]>dis[u]+w[i]&&c[i]){

                 dis[v]=dis[u]+w[i];

                 pre[v]=i;

                 if(!in[v]){

                     q.push(v);

                     in[v]=true;

                 }

             }

         }

     }

     return dis[T]!=dis[];

 }

 void Mcmf(){

     int cost=;

     pre[S]=-;

     while(Spfa()){

         int f=INF;

         for(int i=pre[T];i!=-;i=pre[to[i^]]) f=min(f,c[i]);

         for(int i=pre[T];i!=-;i=pre[to[i^]]){

             c[i]-=f;

             c[i^]+=f;

         }

         cost+=dis[T]*f;

     }

     printf("%d\n",cost);

 }

 int main(){

     n=readint();

     m=readint();

     for(int i=;i<=n;i++) A[i]=readint();

     memset(fir,-,sizeof(fir));

     S=n+;

     T=n+;

     for(int i=;i<=n+;i++){

         if(A[i]>=A[i-]) add(S,i,,A[i]-A[i-]);

         else add(i,T,,A[i-]-A[i]);

         if(i>) add(i,i-,);

     }

     for(int i=;i<=m;i++){

         int a=readint(),

             b=readint(),

             c=readint();

         add(a,b+,c);

     }

     Mcmf();

     return ;

 }