#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=510000;
const ll INF=1e18;
int n,m;
int a[N];
ll sum[N];
struct node{
	int l,r,x;
}b[N];
int f[N];
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
int g[N];
inline int as(int x){
	return x<0?-x:x;
}
ll dp[N];
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].x);
	sort(b+1,b+m+1,[](const node x,const node y){
		return x.x>y.x;
	});
	for(int i=1;i<=n+1;i++)
		f[i]=i;
	ll ans=0;
	for(int i=1,j;i<=m;i=j+1){
		j=i;
		while(j<m&&b[i].x==b[j+1].x)
			j++;
		vector <int> v;
		for(int k=i;k<=j;k++)
			for(int x=find(b[k].l);x<=b[k].r;x=find(x+1)){
				v.push_back(x);
				f[x]=x+1;
			}
		sort(v.begin(),v.end());
		sort(b+i,b+j+1,[](const node x,const node y){
			return x.r<y.r;
		});
		if(v.empty()){
			puts("-1");
			return ;
		}
		for(int k=i;k<=j;k++)
			if(lower_bound(v.begin(),v.end(),b[k].l)==upper_bound(v.begin(),v.end(),b[k].r)){
				puts("-1");
				return ;
			}
		for(int k=0;k<(int)v.size();k++)
			g[k]=0;
		for(int k=i;k<=j;k++){
			int x=lower_bound(v.begin(),v.end(),b[k].l)-v.begin();
			int y=upper_bound(v.begin(),v.end(),b[k].r)-v.begin()-1;
			g[y]=max(g[y],x);
		}
		for(int k=1;k<(int)v.size();k++)
			g[k]=max(g[k],g[k-1]);
		deque <pair<int,int>> q;
		q.push_back(make_pair(-1,0));
		sum[0]=(a[v[0]]<b[i].x?b[i].x-a[v[0]]:0);
		for(int k=1;k<(int)v.size();k++)
			sum[k]=sum[k-1]+(a[v[k]]<b[i].x?b[i].x-a[v[k]]:0);
		for(int k=0;k<(int)v.size();k++){
			if(q.empty()==0&&q.front().first<g[k]-1)
				q.pop_front();
			dp[k]=q.front().second+sum[k-1]+as(a[v[k]]-b[i].x);
			while(q.empty()==0&&q.back().second>=dp[k]-sum[k])
				q.pop_back();
			q.push_back(make_pair(k,dp[k]-sum[k]));
		}
		ll res=INF;
		for(int k=g[(int)v.size()-1];k<(int)v.size();k++)
			res=min(res,dp[k]+sum[(int)v.size()-1]-sum[k]);
		ans+=res;
	}
	printf("%lld\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}