#include <iostream>
#include <cstdio> 
#include <algorithm>
#include <deque>
using namespace std;
typedef long long ll;
const int N=510000;
const ll INF=1e18;
int n,m;
int a[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+1)){
				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+1)-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]);
		dp[0]=as(a[v[0]]-b[i].x);
		deque <pair<int,int>> q;
		q.push_back(make_pair(0,dp[0]));
		for(int k=1;k<(int)v.size();k++){
			if(q.empty()==0&&q.front().first<g[k]-1)
				q.pop_front();
			dp[k]=q.front().second+as(a[v[k]]-b[i].x);
			while(q.empty()==0&&q.back().second<dp[k])
				q.pop_back();
			q.push_back(make_pair(k,dp[k]));
		}
		ll res=INF;
		for(int k=g[(int)v.size()-1];k<(int)v.size();k++)
			res=min(res,dp[k]);
		ans+=res;
	}
	printf("%lld\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}

answer.code: In function ‘void solve()’:
answer.code:39:17: error: ‘vector’ was not declared in this scope
   39 |                 vector <int> v;
      |                 ^~~~~~
answer.code:5:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    4 | #include <deque>
  +++ |+#include <vector>
    5 | using namespace std;
answer.code:39:25: error: expected primary-expression before ‘int’
   39 |                 vector <int> v;
      |                         ^~~
answer.code:42:33: error: ‘v’ was not declared in this scope
   42 |                                 v.push_back(x);
      |                                 ^
answer.code:45:22: error: ‘v’ was not declared in this scope
   45 |                 sort(v.begin(),v.end());
      |                      ^
answer.code:24:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   24 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
answer.code:26:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   26 |                 scanf("%d",&a[i]);
      |                 ~~~~~^~~~~~~~~~~~
answer.code:28:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |                 scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].x);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code: In function ‘int main()’:
answer.code:87:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   87 |         scanf("%d",&T);
      |         ~~~~~^~~~~~~~~