#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=5e5+5,M=N*30+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(time(0));
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,m,fa[N],A[N];
int GF(int x){return fa[x]^x?fa[x]=GF(fa[x]):x;}
struct ques{int l,r,w;}Q[N];
ll dp[N];
int q[N],head,tail;
void Solve(){
	int i,j;scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++) scanf("%d",&A[i]);
	for(i=1;i<=m;i++) scanf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].w);
	iota(fa+1,fa+n+2,1);
	sort(Q+1,Q+m+1,[](ques x,ques y){return x.w^y.w?x.w<y.w:x.r<y.r;});
	ll ans=0;
	for(int l=1,r;l<=m;l=r+1){
		for(r=l;Q[r].w==Q[l].w&&r<=m;r++);r--;
		vector<int> st;
		for(int i=l;i<=r;i++){
			int x=Q[i].l;
			while((x=GF(x))<=Q[i].r){
				st.push_back(x);
				fa[x]=x+1;
				if(A[x]<Q[i].w) ans+=Q[i].w-A[x],A[x]=Q[i].w;
			}
		}
		sort(st.begin(),st.end());
		st.push_back(n+1);A[n+1]=Q[l].w;
		q[head=tail=0]=0;dp[0]=0;
		int R=l;
		for(int j:st){
			while(R<=r&&Q[R].r<j){
				while(head<=tail&&q[head]<Q[R].l) head++;
				R++;
			}
			dp[j]=INF;
			if(head<=tail) dp[j]=dp[q[head]]+A[j]-Q[l].w;
			while(head<=tail&&dp[j]<dp[q[tail]]) tail--;
			q[++tail]=dp[j];
			// gdb(Q[i].w,j,dp[j]);
		}
		ans=min(ans+dp[n+1],INF);
	}
	printf("%lld\n",ans==INF?-1ll:ans);
}
int main(){
	int t=1;
	scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}