#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int T,n,m,a[N],nxt[N];
long long ans,f[N];
struct Node{int l,r,v;}que[N];
vector<pair<int,int>> query;
vector<int> id;
deque<int> q;
int get(int x){
	if(nxt[x]==x)	return x;
	return nxt[x]=get(nxt[x]);
}
void solve(int v){
	while(q.size())	q.pop_back();
	f[0]=0;
	q.push_back(0);
	query.insert(query.begin(),{0,0});
	for(int i:id)	ans+=max(0,v-a[i]);
	id.insert(id.begin(),0);
	long long mn=0x3f3f3f3f3f3f3f3f;
	for(int i=1,j=0;i<=int(id.size())-1;i++){
		while(j<int(query.size())-1&&query[j+1].second<i)	j++;
		while(q.size()&&q.front()<query[j].first)	q.pop_front();
		f[i]=f[q.front()]+max(v,a[id[i]])-v;
		while(q.size()&&f[q.back()]>=f[i])	q.pop_back();
		q.push_back(i);
		if(i>=query.back().first&&i<=query.back().second)	mn=min(mn,f[i]);
	}
	ans+=mn;
}
int main(){
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);	
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)	cin>>a[i];
		for(int i=1;i<=m;i++)	cin>>que[i].l>>que[i].r>>que[i].v;
		for(int i=1;i<=n+1;i++)	nxt[i]=i;
		sort(que+1,que+m+1,[&](const Node &x,const Node &y){
			if(x.v==y.v)	return (x.r==y.r?x.l>y.l:x.r<y.r);
			return x.v>y.v;
		});
		bool flagg=1;
		ans=0;
		for(int i=1;i<=m;i++){
			int l=i,r=i-1;
			query.clear(),id.clear();
			while(r<n&&que[l].v==que[r+1].v){
				r++;
				if(query.empty()||que[r].l>query.back().first)	query.push_back({que[r].l,que[r].r});
			}
			i=r;
			bool flag=1;
			for(pair<int,int> it:query)	if(get(it.first)>it.second)	{flag=0;break;}
			if(!flag){flagg=0;break;}
			for(pair<int,int> it:query)	for(int i=get(it.first);i<=it.second;i=get(i+1))
				id.push_back(i),nxt[i]=get(i+1);
			for(pair<int,int> &it:query){
				it.first=lower_bound(id.begin(),id.end(),it.first)-id.begin()+1;
				it.second=upper_bound(id.begin(),id.end(),it.second)-id.begin();
			}
			solve(que[i].v);
		}
		if(flagg)	cout<<ans<<endl;
		else	cout<<-1<<endl;
	}
	return 0;
}