//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int n,q;
int l[500500],r[500500],v[500500];
int a[500500];
int lim[500500];
vector<int> vq[500500];
vector<int> vec[500500],vlim[500500];
vector<pii> vadd[500500];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>q;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=1;i<=q;i++)
			cin>>l[i]>>r[i]>>v[i];
		multiset<int> ms;
		for(int i=1;i<=n;i++)
			vq[i].clear();
		for(int i=1;i<=q;i++)
		{
			vq[l[i]].pb(v[i]);
			vq[r[i]+1].pb(-v[i]);
		}
		for(int i=1;i<=n;i++)
		{
			for(auto x:vq[i])
				if(x>0)
					ms.insert(x);
				else
					ms.erase(ms.lower_bound(x));
			if(!sz(ms))
				lim[i]=0;
			else
				lim[i]=*ms.rbegin();
		}
		vector<int> pool;
		for(int i=1;i<=n;i++)
			pool.pb(lim[i]);
		srt(pool);
		uni(pool);
		for(int i=1;i<=n;i++)
		{
			vec[i].clear();
			vlim[i].clear();
		}
		bool ok=true;
		for(int i=1;i<=n;i++)
			vec[ub(pool,lim[i])].pb(i);
		for(int i=1;i<=q;i++)
		{
			int p=ub(pool,v[i]);
			if(!p||pool[p-1]!=v[i])
			{
				ok=false;
				break;
			}
			vlim[p].pb(i);
		}
		if(!ok)
		{
			cout<<"-1\n";
			continue;
		}
		ll ans=0;
		for(int i=1;i<=sz(pool);i++)
		{
			int cnt=sz(vec[i]);
			srt(vec[i]);
			vector<int> type(cnt);
			for(int j=0;j<cnt;j++)
				if(lim[vec[i][j]]>=a[vec[i][j]])
					type[j]=1;
			vector<int> psum(cnt);
			for(int j=0;j<cnt;j++)
			{
				psum[j]=type[j];
				if(j) psum[j]+=psum[j-1];
			}
			vector<pii> ranges;
			for(auto ind:vlim[i])
			{
				int L=l[ind],R=r[ind];
				int lp=lb(vec[i],L),rp=ub(vec[i],R)-1;
				if(lp>rp)
				{
					ok=false;
					break;
				}
				if(psum[rp]==(lp?psum[lp-1]:0))
					ranges.pb(lp,rp);
			}
			if(!ok) break;
			vector<int> vm(cnt,inf);
			for(auto pr:ranges)
				vm[pr.first]=min(vm[pr.first],pr.second);
			for(int i=cnt-1;i;i--)
				vm[i-1]=min(vm[i-1],vm[i]);
			for(int j=0;j<=cnt;j++)
				vadd[j].clear();
			vector<int> dp(cnt+1,inf);
			vadd[0].pb(0,1);
			vadd[1].pb(0,-1);
			multiset<int> ms;
			for(int j=0;j<=cnt;j++)
			{
				for(auto pr:vadd[j])
					if(pr.second>0)
						ms.insert(pr.first);
					else
						ms.erase(ms.lower_bound(pr.first));
				if(sz(ms))
					dp[j]=*ms.begin();
				if(j)
					dp[j]+=a[vec[i][j-1]]-lim[vec[i][j-1]];
				if(j==cnt) break;
				int lim=vm[j]+1;
				lim=min(lim,cnt);
				vadd[j+1].pb(dp[j],1);
				vadd[lim+1].pb(dp[j],-1);
			}
			int rval=inf;
			for(int j=0;j<=cnt;j++)
				if(j==cnt||vm[j]>cnt)
					rval=min(rval,dp[j]);
			if(rval==inf)
				ok=false;
			ans+=rval;
		}
		for(int i=1;i<=n;i++)
			if(lim[i]>=a[i])
				ans+=lim[i]-a[i];
		if(ok)
			cout<<ans<<'\n';
		else
			cout<<"-1\n";
	}
	return 0;
}