#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
    x=0;char c=getchar();bool f=0;
    for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
    x=(f?-x:x);
}
const int N = 5e5+7;
int n,q,m,a[N],ql[N],qr[N],lim[N];
int seg_mx[N*4];
void ckmax(int &x,int v){x=max(x,v);}
void ckmin(int &x,int v){x=min(x,v);}
void modify(int k,int l,int r,int L,int R,int v)
{
    if(L<=l&&r<=R)
    {
        ckmax(seg_mx[k],v);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)modify(k<<1,l,mid,L,R,v);
    if(R>mid)modify(k<<1|1,mid+1,r,L,R,v);
}
int up[N];
void build(int k,int l,int r,int v)
{
    v=max(v,seg_mx[k]);
    seg_mx[k]=0;
    if(l==r)
    {
        up[l]=v;
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid,v);
    build(k<<1|1,mid+1,r,v);
}
vector<int> vecp[N*2],vecq[N*2];
int dct[N*2],tot=0;
typedef long long LL;
int pos[N];
vector<int> vec[N];
LL dp[5050];
int que[N];
LL solve(int W)
{
    m=0;
    for(int x:vecp[W])pos[++m]=x;
    for(int i=1;i<=m;i++)vec[i].clear();
    for(int i:vecq[W])
    {
        int l=ql[i],r=qr[i];
        l=lower_bound(pos+1,pos+m+1,l)-pos;
        r=upper_bound(pos+1,pos+m+1,r)-pos-1;
        if(l>r)return -1;
        vec[r].push_back(l);
    }
    dp[0]=0;
    int l=1,r=0;
    que[++r]=0;
    LL tag=0;
    for(int i=1;i<=m;i++)
    {
        int cur=a[pos[i]];
        LL v=dp[que[l]]+tag;
        tag+=(cur>=W?0:dct[W]-dct[cur]);
        dp[i]=v+abs(dct[W]-dct[cur])-tag;
        while(l<=r&&dp[que[r]]>dp[i])r--;
        que[++r]=i;
        int mxr=0;
        for(int vr:vec[i])mxr=max(mxr,vr);
        while(l<=r&&que[l]<mxr)l++;
    }
    LL ans=dp[que[l]]+tag;
    return ans;
}
void solve()
{
    read(n);read(q);
    tot=0;
    for(int i=1;i<=n;i++)read(a[i]),dct[++tot]=a[i];
    for(int i=1;i<=q;i++)
    {
        read(ql[i]);
        read(qr[i]);
        read(lim[i]);
        dct[++tot]=lim[i];
    }
    sort(dct+1,dct+tot+1);
    tot=unique(dct+1,dct+tot+1)-dct-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(dct+1,dct+tot+1,a[i])-dct;
    for(int i=1;i<=q;i++)
    {
        lim[i]=lower_bound(dct+1,dct+tot+1,lim[i])-dct;
        modify(1,1,n,ql[i],qr[i],lim[i]);
    }
    build(1,1,n,1);
    for(int i=1;i<=tot;i++)
    {
        vecp[i].clear();
        vecq[i].clear();
    }
    LL res=0;
    for(int i=1;i<=n;i++)vecp[up[i]].push_back(i);
    for(int i=1;i<=q;i++)vecq[lim[i]].push_back(i);
    for(int i=1;i<=tot;i++)
    {
        LL v=solve(i);
        if(v==-1)
        {
            res=-1;
            break;
        }
        res+=v;
    }
    printf("%lld\n",res);
}
int main()
{
    freopen("a.in","r",stdin);
    int t;
    read(t);
    while(t--)
    {
        solve();
    }
    return 0;
}