/**************************************************************

    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.