#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int T,n,m,a[N];
long long ans,f[N];
struct Node{int l,r,v;}que[N];
vector<pair<int,int>> query;
vector<int> id,liveid;
deque<int> q;
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(){
	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;
		liveid.clear();
		for(int i=1;i<=n+1;i++)	liveid.push_back(i);
		sort(que+1,que+m+1,[&](const Node &x,const Node &y){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++,query.push_back({que[r].l,que[r].r});
			i=r;
			sort(query.begin(),query.end(),[&](const pair<int,int> &x,const pair<int,int> &y){
				return (x.second==y.second?x.first>y.first:x.second<y.second);
			});
			for(int i=0;i<int(query.size());i++)
				if(i&&query[i].first<=query[i-1].first)	query.erase(query.begin()+i),i--;
			bool flag=1;
			for(pair<int,int> it:query)
				if(*lower_bound(liveid.begin(),liveid.end(),it.first)>it.second)	flag=0;
			if(!flag){flagg=0;break;}
			for(pair<int,int> it:query){
				vector<int>::iterator nowl=lower_bound(liveid.begin(),liveid.end(),it.first),nowr;
				for(nowr=nowl;(*nowr)<=it.second;nowr++)	id.push_back(*nowr);
				liveid.erase(nowl,nowr);
			}
			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;
}