#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]=-1;
		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();
			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++){
			while(q.empty()==0&&q.front().first<g[k])
				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()];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;
}

answer.code: In function ‘int main()’:
answer.code:85:12: error: expected primary-expression before ‘=’ token
   85 | int main(){=
      |            ^
answer.code:86:9: error: expected primary-expression before ‘int’
   86 |         int T;
      |         ^~~
answer.code:87:21: error: ‘T’ was not declared in this scope
   87 |         scanf("%d",&T);
      |                     ^
answer.code: In function ‘void solve()’:
answer.code:22:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   22 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
answer.code:24:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   24 |                 scanf("%d",&a[i]);
      |                 ~~~~~^~~~~~~~~~~~
answer.code:26:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   26 |                 scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].x);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~