#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
#define pb emplace_back
using namespace std;
const int N = 1 << 20;
int n, m;
int a[N];
int l[N], r[N], v[N];
int arr[N], tot;
int tag[N];
void upd(int x, int L, int R, int l, int r, int w) {
	if(l <= L && R <= r) {
		tag[x] = max(tag[x], w);
		return;
	}
	int mid = (L + R) >> 1;
	if(l <= mid) upd(x * 2, L, mid, l, r, w);
	if(r > mid) upd(x * 2 + 1, mid + 1, R, l, r, w);
}
int b[N];
void push(int x, int L, int R) {
	if(L == R) {
		b[L] = tag[x];
		return;
	}
	int mid = (L + R) >> 1;
	tag[x * 2] = max(tag[x * 2], tag[x]);
	tag[x * 2 + 1] = max(tag[x * 2 + 1], tag[x]);
	push(x * 2, L, mid);
	push(x * 2 + 1, mid + 1, R);
}
vi use[N];
vector<pair<int,int>>con[N];
int pos[N], lst[N], all;
ll cost[N];
ll dp[N];
ll mn[N];
void build(int x, int L, int R) {
	mn[x] = 1e18;
	if(L == R)
		return void();
	int mid = (L + R) >> 1;
	build(x * 2, L, mid);
	build(x * 2 + 1, mid + 1, R);
}
void gai(int x, int L, int R, int p, ll w) {
	mn[x] = min(mn[x], w);
	if(L == R) return void();
	int mid = (L + R) >> 1;
	p <= mid ? gai(x * 2, L, mid, p, w) : gai(x * 2 + 1, mid + 1, R, p, w);
}
ll query(int x, int L, int R, int l, int r) {
	if(l <= L && R <= r) return mn[x];
	ll ans = 1e18;
	int mid = (L + R) >> 1;
	if(l <= mid) ans = min(ans, query(x * 2, L, mid, l, r));
	if(r > mid) ans = min(ans, query(x * 2 + 1, mid + 1, R, l, r));
	return ans;
}
void Main() {
	cin >> n >> m;
	L(i, 1, n) {
		cin >> a[i];
	}
	tot = 0;
	L(i, 1, m) {
		cin >> l[i] >> r[i] >> v[i];
		arr[++tot] = v[i];
	}
	sort(arr + 1, arr + tot + 1);
	tot = unique(arr + 1, arr + tot + 1) - arr - 1;
	L(i, 1, m) {
		v[i] = lower_bound(arr + 1, arr + tot + 1, v[i]) - arr;
		upd(1, 1, n, l[i], r[i], v[i]);
		con[v[i]].pb(l[i], r[i]);
	}
	push(1, 1, n);
	L(i, 1, n) {
		use[b[i]].pb(i);
	}
	int ban = 0;
	ll ans = 0;
	L(i, 1, tot) {
		all = 0;
		for(auto&u : use[i]) {
			pos[++all] = u;
		}
		L(i, 0, all + 1) {
			lst[i] = 0, cost[i] = 0;
		}
		L(i, 1, all) {
			if(arr[b[pos[i]]] > a[pos[i]]) {
				ans += arr[b[pos[i]]] - a[pos[i]];
				cost[i] = 0;
			} else {
				cost[i] = a[pos[i]] - arr[b[pos[i]]];
			}
		}
		for(auto&it : con[i]) {
			int l = lower_bound(pos + 1, pos + all + 1, it.first) - pos;
			int r = upper_bound(pos + 1, pos + all + 1, it.second) - pos - 1;
			if(l > r) {
				ban = 1;
				continue;
			}
			lst[r] = max(lst[r], l);
		}
		R(i, all, 0) {
			lst[i + 1] = max(lst[i + 1], lst[i]);
		}
		build(1, 0, all);
		dp[0] = 0;
		L(j, 1, all + 1) {
			gai(1, 0, all, j - 1, dp[j - 1]);
			dp[j] = query(1, 0, all, lst[j - 1], j - 1) + cost[j];
		}
		ans += dp[all + 1];
	}
	if(ban) {
		cout << -1 << '\n';
	} else {
		cout << ans << '\n';
	}
	L(i, 0, min(n * 4, N - 1)) 
		tag[i] = a[i] = b[i] = 0, use[i].clear(), con[i].clear(), l[i] = r[i] = v[i] = 0; 

}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin >> t; while(t--) Main();
	return 0;
} 
/*
1
3 2
2023 40 41
1 1 2022
2 2 39
*/