#include<bits/stdc++.h>
using namespace std;
int n,m,a[501000],qc[501000],l[501000],r[500100],v[501000],cn,b[500100],fa[500100];
vector<int>g1[501000],g2[500100];
#define ll long long
#define pb push_back
int F(int x){if(x==fa[x])return x;return fa[x]=F(fa[x]);}
int cy[501000],e,L[501000];
ll ans,dp[501000];
int sta[500100],fl,fr;
void sol(){
    ans=0,scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=-1;
    for(int i=1;i<=n+1;i++)fa[i]=i;
    cn=0;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&l[i],&r[i],&v[i]);
        qc[++cn]=v[i];
    }
    sort(qc+1,qc+cn+1);cn=unique(qc+1,qc+cn+1)-qc-1;
    for(int i=1;i<=cn;i++)g1[i].clear(),g2[i].clear();
    for(int i=1;i<=m;i++)
        v[i]=lower_bound(qc+1,qc+cn+1,v[i])-qc,g1[v[i]].pb(i);
    for(int i=cn;i;i--)for(int o:g1[i]){
        int u=F(l[o]),v=F(r[o]+1);
        while(u!=v)fa[u]=F(u+1),b[u]=i,u=fa[u];
    }
    for(int i=1;i<=n;i++)g2[b[i]].pb(i);
    for(int v=1;v<=cn;v++){
        e=0;for(int j:g2[v])cy[++e]=j;
        for(int i=1;i<=e;i++)L[i]=0;
        for(int j:g1[v]){
            int x=lower_bound(cy+1,cy+e+1,l[j])-cy,y=lower_bound(cy+1,cy+e+1,r[j]+1)-cy-1;
            if(x<=y)L[y]=max(L[y],x);
            else{puts("-1");return;}
        }
        fl=fr=1,sta[1]=0;
        ll mi=1e18;
        for(int i=1;i<=e;i++){
            L[i]=max(L[i],L[i-1]);int a_;
            if(a[cy[i]]<qc[v])a_=0,ans+=qc[v]-a[cy[i]];
            else a_=a[cy[i]]-qc[v];
            while(fl<=fr&&sta[fl]<L[i-1])fl++;dp[i]=dp[sta[fl]]+a_;
            while(fl<=fr&&dp[sta[fr]]>=dp[i])fr--;sta[++fr]=i;
            if(L[e]<=i)mi=min(mi,dp[i]);
        }
        ans+=mi;
    }
    printf("%lld\n",ans);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}