#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];
ostream& operator << (ostream &out,opts a){
	return out<<make_tuple(a.l,a.r,a.v);
}
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],s[N],q[N];
ll f[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

answer.code: In function ‘std::ostream& operator<<(std::ostream&, opts)’:
answer.code:22:19: error: no match for ‘operator<<’ (operand types are ‘std::ostream’ {aka ‘std::basic_ostream<char>’} and ‘std::tuple<int, int, int>’)
   22 |         return out<<make_tuple(a.l,a.r,a.v);
      |                ~~~^~~~~~~~~~~~~~~~~~~~~~~~~
      |                |              |
      |                |              std::tuple<int, int, int>
      |                std::ostream {aka std::basic_ostream<char>}
In file included from /usr/include/c++/13/istream:41,
                 from /usr/include/c++/13/sstream:40,
                 from /usr/include/c++/13/complex:45,
                 from /usr/include/c++/13/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127,
                 from answer.code:1:
/usr/include/c++/13/ostream:110:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(__ostream_type& (*)(__ostream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  110 |       operator<<(__ostream_type& (*__pf)(__ostream_type&))
      |       ^~~~~~~~
/usr/include/c++/13/ostream:110:36: note:   no known conversion for argument 1 from ‘std::tuple<int, int, int>’ to ‘std::basic_ostream<char>::__ostream_type& (*)(std::basic_ostream<char>::__ostream_type&)’ {aka ‘std::basic_ostream<char>& (*)(std::basic_ostream<char>&)’}
  110 |       operator<<(__ostream_type& (*__pf)(__ostream_type&))
      |                  ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/ostream:119:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(__ios_type& (*)(__ios_type&)) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>; __ios_type = std::basic_ios<char>]’
  119 |       operator<<(__ios_type& (*__pf)(__ios_type&))
      |       ^~~~~~~~
/usr/include/c++/13/ostream:119:32: note:   no known conversion for argument 1 from ‘std::tuple<int, int, int>’ to ‘std::basic_ostream<char>::__ios_type& (*)(std::basic_ostream<char>::__ios_type&)’ {aka ‘std::basic_ios<char>& (*)(std::basic_ios<char>&)’}
  119 |       operator<<(__ios_type& (*__pf)(__ios_type&))
      |                  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
/usr/include/c++/13/ostream:129:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(std::ios_base& (*)(std::ios_base&)) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  129 |       operator<<(ios_base& (*__pf) (ios_base&))
      |       ^~~~~~~~
/usr/include/c++/13/ostream:129:30: note:   no known conversion for argument 1 from ‘std::tuple<int, int, int>’ to ‘std::ios_base& (*)(std::ios_base&)’
  129 |       operator<<(ios_base& (*__pf) (ios_base&))
      |                  ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/13/ostream:168:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  168 |       operator<<(long __n)
      |       ^~~~~~~~
/usr/include/c++/13/ostream:168:23: note:   no known conversion for argument 1 from ‘std::tuple<int, int, int>’ to ‘long int’
  168 |       operator<<(long __n)
      |                  ~~~~~^~~
/usr/include/c++/13/ostream:172:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  172 |       operator<<(unsigned long __n)
      |       ^~~~~~~~
/usr/include/c++/13/ostream:172:32: note:   no known conversion for argument 1 from ‘std::tuple<int, int, int>’ to ‘long unsigned int’
  172 |       operator<<(unsigned long __n)
      |                  ~~~~~~~~~~~~~~^~~
/usr/include/c++/13/ostream:176:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  176 |       operator<<(bool __n)
      |       ^~~~~~~~
/usr/include/c++/13/ostream:176:23: note:   no known conversion for argument 1 from ‘std::tuple<int, int, int>’ to ‘bool’
  176 |       operator<<(bool __n)
      |                  ~~~~~^~~
In file included from /usr/include/c++/13/ostream:880:
/usr/include/c++/13/bits/ostream.tcc:96:5: note: candidate: ‘std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(short int) [with _CharT = char; _Traits = std::char_traits<char>]’
   96 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/ostream.tcc:...