#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5;
const ll inf=1ll<<60;
int n,m;
int a[N+5];
struct Que{
    int l,r,v;
    Que(int l=0,int r=0,int v=0):l(l),r(r),v(v){}
}b[N+5];
int f[N+5];
ll ans;
int find(int x){ return x==f[x]?x:f[x]=find(f[x]); }
bool cmp(Que x,Que y){ return x.v>y.v; }
struct Segtr{
    ll tr[N*4+5];
    #define lc id<<1
    #define rc id<<1|1
    void build(int l,int r,int id){
        tr[id]=inf;
        if(l==r) return;
        int mid=l+r>>1;
        build(l,mid,lc);
        build(mid+1,r,rc);
    }
    ll query(int l,int r,int st,int en,int id){
        if(st<=l&&en>=r) return tr[id];
        int mid=l+r>>1; ll ans=inf;
        if(st<=mid) ans=min(ans,query(l,mid,st,en,lc));
        if(en>mid) ans=min(ans,query(mid+1,r,st,en,rc));
        return ans;
    }
    void change(int l,int r,int p,ll x,int id){
        if(l==r){
            tr[id]=x;
            return;
        }
        int mid=l+r>>1;
        if(p<=mid) change(l,mid,p,x,lc);
        else change(mid+1,r,p,x,rc);
    }
}T;
bool work(int l,int r,int v){
    static int mxl[N+5];
    static int pos[N+5];
    int ps=0;
    for(int i=l;i<=r;i++){
        int j=find(b[i].l);
        while(j<=b[i].r){
            pos[++ps]=j;
            f[j]=j+1; j=find(j);
        }
    }
    sort(pos+1,pos+1+ps);
    fill(mxl+1,mxl+1+ps,0);
    for(int i=l;i<=r;i++){
        int ll=lower_bound(pos+1,pos+1+ps,b[i].l)-pos;
        int rr=upper_bound(pos+1,pos+1+ps,b[i].r)-pos-1;
        if(ll>rr) return 0;
        mxl[rr]=max(mxl[rr],ll);
    }
    T.build(0,ps,1);
    T.change(0,ps,0,0,1);
    int ql=0;
    for(int i=1;i<=ps;i++){
        int p=pos[i];
        ql=max(ql,mxl[i-1]);
        ll val=T.query(0,ps,ql,i-1,1)+abs(v-a[p]);
        T.change(0,ps,i,val,1);
        if(a[i]<=v) ql=i;
    }
    ql=max(ql,mxl[ps]);
    ans+=T.query(0,ps,ql,ps,1);
    return 1;
}
void solve(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%d %d %d",&b[i].l,&b[i].r,&b[i].v); 
    for(int i=1;i<=n+1;i++) f[i]=i;
    ans=0;
    sort(b+1,b+1+m,cmp);
    for(int i=1,j;i<=m;i=j){
        for(j=i;j<=m&&b[j].v==b[i].v;j++);
        if(!work(i,j-1,b[i].v)){
            puts("-1");
            return;
        }
    }
    printf("%lld\n",ans);
}
int main(){
    int t; scanf("%d",&t);
    while(t--) solve();
    return 0;
}