#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=5e5+1e3+7;

int T;

int n,m,c[N],a[N];

int l[N],r[N],v[N];

vector<int> p[N];

map<int,vector<pair<int,int> >>seg;

map<int,vector<int> >seq;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>a[i],p[i].clear();
        seg.clear();
        for(int i=1;i<=m;i++)
        {
            cin>>l[i]>>r[i]>>v[i];
            seg[v[i]].push_back({l[i],r[i]});
            p[l[i]].push_back(v[i]);
            p[r[i]+1].push_back(-v[i]);
        }
        multiset<int> s;
        for(int i=1;i<=n;i++)
        {
            for(auto x:p[i])
                if(x<0)
                    s.erase(s.find(-x));
                else
                    s.insert(x);
            if(s.size())
                c[i]=*prev(s.end());
            else
                c[i]=1;
        }
        seq.clear();
        for(int i=1;i<=n;i++)
            seq[-c[i]].push_back(i);
        int ans=0;
        for(auto [tx,v]:seq)
        {
            int x=-tx;
            int m=v.size();
            vector<int> s(m+1);
            vector<int> f(m+1);
            vector<int> mxl(m+1);
            for(auto &[l,r]:seg[x])
            {
                l=lower_bound(v.begin(),v.end(),l)-v.begin()+1;
                r=upper_bound(v.begin(),v.end(),r)-v.begin();
                mxl[r]=max(mxl[r],l);
            }
            for(int i=1;i<=m;i++)
                mxl[i]=max(mxl[i],mxl[i-1]);
            for(int i=1;i<=m;i++)
            {
                s[i]=s[i-1];
                if(x>a[v[i-1]])
                    s[i]+=x-a[v[i-1]];
            }
            deque<int> q;
            q.push_back(0);
            for(int i=1;i<=m;i++)
            {
                f[i]=1e18;
                while(q.size()&&q.front()<mxl[i-1])
                    q.pop_front();
                if(q.size())
                    f[i]=f[q.front()]-s[q.front()]+s[i-1]+abs(x-a[v[i-1]]);
                while(q.size()&&f[i]-s[i]<f[q.back()]-s[q.back()])
                    q.pop_back();
                q.push_back(i);
            }
            int mn=1e18;
            for(int i=mxl[m];i<=m;i++)
                mn=min(mn,f[i]);
            ans+=mn;
            ans=min(ans,(int)1e18);
        }
        if(ans>1e17)
            cout<<"-1\n";
        else
            cout<<ans<<"\n";
    }
}