#include<bits/stdc++.h>
using namespace std;
constexpr int N=500005;
constexpr long long INF=1e18;
int n,m;
int a[N];
struct Seg
{
    int l,r,v;
}s[N];
int pos[N],tot;
int nxt[N];
int getf(int v)
{
    if(v==nxt[v]) return v;
    else return nxt[v]=getf(nxt[v]);
}
int pre[N];
long long f[N];
long long solve(vector<pair<int,int>>seg,int v)
{
    tot=0;
    for(auto [l,r]:seg)
    {
        for(int x=getf(l);x<=r;x=nxt[x])
        {
            pos[++tot]=x;
            nxt[x]=getf(x+1);
        }
    }
    sort(pos+1,pos+tot+1);
    for(int i=1;i<=tot;i++)
        pre[i]=0;
    for(auto [l,r]:seg)
    {
        int ll=lower_bound(pos+1,pos+tot+1,l)-pos;
        int rr=upper_bound(pos+1,pos+tot+1,r)-pos-1;
        if(ll>rr) return -1;
        pre[rr]=max(pre[rr],ll);
    }
    int lst=0;
    f[0]=0;
    for(int i=1;i<=tot;i++)
    {
        lst=max(lst,pre[i-1]);
        f[i]=INF;
        for(int j=lst;j<=i;j++)
            f[i]=min(f[i],f[j]+abs(a[pos[i]]-v));
        if(a[pos[i]]<v) lst=i;
    }
    lst=max(lst,pre[tot]);
    long long res=INF;
    for(int i=lst;i<=tot;i++)
        res=min(res,f[i]);
    return res;
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>s[i].l>>s[i].r>>s[i].v;
    for(int i=1;i<=n+1;i++)
        nxt[i]=i;
    sort(s+1,s+m+1,[](const Seg &x,const Seg &y){return x.v<y.v;});
    long long ans=0;
    for(int i=1,j=1;i<=m;i=j)
    {
        while(j<=m&&s[i].v==s[j].v) j++;
        vector<pair<int,int>>seg;
        for(int k=i;k<j;k++)
            seg.emplace_back(s[k].l,s[k].r);
        long long sum=solve(seg,s[i].v);
        if(sum==-1)
        {
            cout<<-1<<"\n";
            return;
        }
        ans+=sum;
    }
    cout<<ans<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}