#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned ll;
const int N=5e5+10;
const ll INF=1e18;
int T,n,m,a[N],lim[N];
struct opts{
	int l,r,v;
}o[N];
#ifdef DEBUG
ostream& operator << (ostream &out,opts a){
	return out<<make_tuple(a.l,a.r,a.v);
}
#endif
namespace SGT{
	int t[N<<2];
	void build(int l=1,int r=n,int rt=1){
		t[rt]=1;
		if(l==r)return;
		int mid=(l+r)>>1;
		build(l,mid,rt<<1);
		build(mid+1,r,rt<<1|1);
	}
	void update(int L,int R,int x,int l=1,int r=n,int rt=1){
		if(L<=l&&r<=R)return t[rt]=max(t[rt],x),void();
		int mid=(l+r)>>1;
		if(L<=mid)update(L,R,x,l,mid,rt<<1);
		if(mid<R)update(L,R,x,mid+1,r,rt<<1|1);
	}
	void push(int l=1,int r=n,int rt=1,int x=1){
		x=max(x,t[rt]);
		if(l==r)return lim[l]=x,void();
		int mid=(l+r)>>1;
		push(l,mid,rt<<1,x);
		push(mid+1,r,rt<<1|1,x);
	}
}
int cur[N],mx[N],q[N];
ll f[N],s[N];
void get(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	SGT::build();
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&o[i].l,&o[i].r,&o[i].v);
		SGT::update(o[i].l,o[i].r,o[i].v);
	}
	SGT::push(),lim[n+1]=0;
	iota(cur,cur+1+n,0);
	sort(cur+1,cur+1+n,[&](int x,int y){
		return lim[x]^lim[y]?lim[x]<lim[y]:x<y;
	});
	sort(o+1,o+1+m,[&](opts x,opts y){
		if(x.v^y.v)return x.v<y.v;
		return x.r<y.r;
	});
	ll ans=0;
	// debug(ary(lim,1,n));
	for(int l=1,r,x=1,y;l<=m;l=r,x=y){
		for(r=l+1;r<=m&&o[l].v==o[r].v;r++);
		for(y=x;y<=n&&lim[cur[y]]==o[l].v;y++);
		// debug(ary(o,l,r-1),ary(cur,x,y-1));
		if(y==x)return puts("-1"),void();
		cur[x-1]=0;
		int ne=n+1;
		swap(ne,cur[y]);
		mx[l-1]=s[x-1]=0;
		for(int i=l;i<r;i++)mx[i]=max(mx[i-1],o[i].l);
		for(int i=x;i<y;i++)s[i]=s[i-1]+max(lim[cur[i]]-a[cur[i]],0);
		// debug(ary(s,x,y));
		int L=1,R=1;
		q[R]=x-1;
		fill(f+x,f+1+y,INF),f[x-1]=0;
		for(int i=x,p=l;i<=y;i++){
			for(;p<r&&o[p].r<cur[i];p++);
			for(;L<=R&&cur[q[L]]<mx[p-1];L++);
			if(L<=R){
				f[i]=f[q[L]]+s[i-1]-s[q[L]]+abs(lim[cur[i]]-a[cur[i]]);
				for(;L<=R&&f[q[R]]-s[q[R]]<=f[i]-s[i];R--);
				q[++R]=i;
			}
		}
		if(f[y]==INF)return puts("-1"),void();
		ans+=f[y];
		swap(ne,cur[y]);
	}
	printf("%lld\n",ans);
}
int main(){
	for(scanf("%d",&T);T--;)get();
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif