#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define ldb long double
#define pii pair<int,int>
#define mkp make_pair
#define mkt make_tuple
#define fr first
#define se second
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define all(_box) _box.begin(),_box.end()
#define ppc __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
#define lbd lower_bound
#define ubd upper_bound
#define deb(x) cerr<<#x<<'='<<(x)<<' '
using namespace std;
const int N=5e5+4;
int n,m;
int a[N],b[N];
struct node{
    int l,r,x;
}c[N];
int mx[N];
ll f[N];

namespace MFS{
    int fa[N];

    void init(){
        iota(fa+1,fa+n+2,1);
    }
    int find(int u){
        return u==fa[u]?u:fa[u]=find(fa[u]);
    }
    void merge(int u,int v){
        fa[find(v)]=find(u);
    }
}
using MFS::find;
using MFS::merge;

bool solve(){
    cin>>n>>m;
    MFS::init();
    fill(b+1,b+n+1,0);
    for(int i=1;i<=n;i++)cin>>a[i];
    map<int,vector<pii>>qy;
    for(int i=1;i<=m;i++){
        cin>>c[i].l>>c[i].r>>c[i].x;
        qy[c[i].x].push_back({c[i].l,c[i].r});
    }
    sort(c+1,c+m+1,[](const node &u,const node &v){
        return u.x<v.x;
    });

    ll ans=0;
    map<int,vector<int>>pos;
    for(int i=m;i>=1;i--)
        for(int j=c[i].l;(j=find(j))<=c[i].r;j++){
            pos[b[j]=c[i].x].push_back(j),merge(j+1,j);
            if(a[j]<b[j])ans+=b[j]-a[j],a[j]=b[j];
        }
    
    for(const auto &i:qy)
        if(pos[i.fr].empty())return 0;
    
    for(const auto &i:pos){
        auto &arr=i.se;
        int len=arr.size();
        fill(mx+1,mx+len+1,0);
        for(const auto &j:qy[i.fr]){
            int l=lbd(all(arr),j.fr)-arr.begin()+1;
            int r=lbd(all(arr),j.se)-arr.begin()+1;
            mx[r]=max(mx[r],l);
        }

        deque<int>q({0});
        for(int j=1;j<=len;j++){
            mx[j]=max(mx[j],mx[j-1]);
            while(!q.empty()&&q.front()<mx[j-1])q.pop_front();
            if(q.empty())return 0;
            int pos=arr[q.front()];
            f[j]=f[q.front()]+a[pos]-b[pos];
            while(!q.empty()&&f[j]<f[q.back()])q.pop_back();
            q.push_back(j);
        }
        ans+=*min_element(f+mx[len],f+len+1);
    }
    cout<<ans<<'\n';
    return 1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int T;
    cin>>T;
    while(T--){
        if(solve());
        else cout<<-1<<'\n';
    }
}