#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<deque>
#include<stack>
#include<unordered_map>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int N=5e5+10;
struct node
{
	int l,r,v;
}q[N];
int n,m,a[N],b[N],tr[N<<2],laz[N<<2];
void build(int k,int l,int r)
{
	if(l==r)
	{
		tr[k]=laz[k]=0;
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	tr[k]=laz[k]=0;
	return;
}
void modify(int k,int l,int r,int al,int ar,int v)
{
	if(al<=l&&r<=ar)
	{
		laz[k]=max(laz[k],v);
		return;
	}
	int mid=(l+r)>>1;
	if(al<=mid) modify(k<<1,l,mid,al,ar,v);
	if(ar>=(mid+1)) modify(k<<1|1,mid+1,r,al,ar,v);
	return;
}
int query(int k,int l,int r,int x)
{
	if(l==r) return laz[k];
	int mid=(l+r)>>1,res=laz[k];
	if(x<=mid) res=max(res,query(k<<1,l,mid,x));
	else res=max(res,query(k<<1|1,mid+1,r,x));
	return res;
}
void build1(int k,int l,int r)
{
	if(l==r)
	{
		tr[k]=b[l];
		return;
	}
	int mid=(l+r)>>1;
	build1(k<<1,l,mid);
	build1(k<<1|1,mid+1,r);
	tr[k]=min(tr[k<<1],tr[k<<1|1]);
	return;
}
int query1(int k,int l,int r,int al,int ar)
{
	if(al<=l&&r<=ar) return tr[k];
	int mid=(l+r)>>1,res=1e9;
	if(al<=mid) res=min(res,query1(k<<1,l,mid,al,ar));
	if(ar>=(mid+1)) res=min(res,query1(k<<1|1,mid+1,r,al,ar));
	return res;
}
int lsh[N];
vector<int>p1[N],p2[N],p3[N];
bool cmp(int a,int b){return q[a].r==q[b].r?q[a].l>q[b].l:q[a].r<q[b].r;}
ll TR[N<<2];
void build2(int k,int l,int r)
{
	if(l==r)
	{
		TR[k]=1e18;
		return;
	}
	int mid=(l+r)>>1;
	build2(k<<1,l,mid);
	build2(k<<1|1,mid+1,r);
	TR[k]=1e18;
	return;
}
void modify2(int k,int l,int r,int x,ll v)
{
	if(l==r)
	{
		TR[k]=min(TR[k],v);
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) modify2(k<<1,l,mid,x,v);
	else modify2(k<<1|1,mid+1,r,x,v);
	TR[k]=min(TR[k<<1],TR[k<<1|1]);
	return;
}
ll query2(int k,int l,int r,int al,int ar)
{
	if(al<=l&&r<=ar) return TR[k];
	int mid=(l+r)>>1;ll res=1e18;
	if(al<=mid) res=min(res,query2(k<<1,l,mid,al,ar));
	if(ar>=(mid+1)) res=min(res,query2(k<<1|1,mid+1,r,al,ar));
	return res;
}
void modify3(int k,int l,int r,int x)
{
	if(l==r)
	{
		TR[k]=1e18;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) modify3(k<<1,l,mid,x);
	else modify3(k<<1|1,mid+1,r,x);
	TR[k]=min(TR[k<<1],TR[k<<1|1]);
	return;
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		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",&q[i].l,&q[i].r,&q[i].v);
		build(1,1,n);
		for(int i=1;i<=m;i++)
			modify(1,1,n,q[i].l,q[i].r,q[i].v);
		for(int i=1;i<=n;i++) b[i]=query(1,1,n,i);
//		for(int i=1;i<=n;i++) printf("b[%d]=%d ",i,b[i]);puts("");
		build1(1,1,n);
		bool check=1;
		for(int i=1;i<=m;i++)
			if(query1(1,1,n,q[i].l,q[i].r)!=q[i].v) check=0;
		if(!check)
		{
			puts("-1");
			continue;
		}
		ll ans=0;
		for(int i=1;i<=n;i++) if(a[i]<b[i]) ans+=b[i]-a[i],a[i]=b[i];
		for(int i=1;i<=m;i++) lsh[i]=q[i].v;
		sort(lsh+1,lsh+m+1);int m1=unique(lsh+1,lsh+m+1)-lsh-1;
		for(int i=1;i<=n;i++) b[i]=lower_bound(lsh+1,lsh+m1+1,b[i])-lsh;
		for(int i=1;i<=m;i++) q[i].v=lower_bound(lsh+1,lsh+m1+1,q[i].v)-lsh;
		for(int i=1;i<=m1;i++) p1[i].clear(),p2[i].clear();
		for(int i=1;i<=n;i++) p1[b[i]].push_back(i);
		for(int i=1;i<=m;i++) p3[q[i].v].push_back(i);
		build2(1,1,n);
		for(int i=1;i<=m1;i++)
		{
			sort(p3[i].begin(),p3[i].end(),cmp);
			int mxl=0;
			for(int j=0;j<p3[i].size();j++)
			{
				if(mxl<q[p3[i][j]].l) p2[i].push_back(p3[i][j]);
				mxl=max(mxl,q[p3[i][j]].l);
			}
			sort(p2[i].begin(),p2[i].end(),cmp);
			for(int j=0,k=0;j<p2[i].size();j++)
			{
				while(k<p1[i].size()&&p1[i][k]<q[p2[i][j]].l) k++;
				int tk=k;
				while(k<p1[i].size()&&p1[i][k]<=q[p2[i][j]].r) k++;
//				printf("l=%d r=%d\n",tk,k-1);
				if(j==0)
				{
					for(int k1=tk;k1<=k-1;k1++)
					{
						modify2(1,1,n,p1[i][k1],a[p1[i][k1]]-lsh[i]);
//						printf("x=%d d=%d\n",p1[i][k1],a[p1[i][k1]]-lsh[i]);
					}
				}
				else
				{
					ll op=query2(1,1,n,q[p2[i][j-1]].l,q[p2[i][j-1]].r);
					for(int k1=tk;k1<=k-1;k1++) modify2(1,1,n,p1[i][k1],op+a[p1[i][k1]]-lsh[b[p1[i][k1]]]);
				}
				if(j==(p2[i].size()-1)) ans+=query2(1,1,n,q[p2[i][j]].l,q[p2[i][j]].r);
			}
			for(int j=0;j<p1[i].size();j++) modify3(1,1,n,p1[i][j]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}