#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5;
int n, m, lef[N + 5], L[N + 5], R[N + 5], X[N + 5], pl[N + 5];
int fa[N + 5], a[N + 5], q[N + 5];
int tn, pos[N + 5], tq, nd[N + 5], mxl[N + 5];
ll f[N + 5], ans;
void Clear() {
	for (int i = 0; i <= max(n, m); i++) lef[i] = pl[i] = fa[i] = 0;
}
int gf(int x) { return x == fa[x] ? x : fa[x] = gf(fa[x]); }
ll Solve_v(int V) {
	sort(pos + 1, pos + tn + 1);
	fill(mxl, mxl + tn + 1, 0);
	for (int i = 1; i <= tq; i++) {
		int l = lower_bound(pos + 1, pos + tn + 1, L[nd[i]]) - pos;
		int r = upper_bound(pos + 1, pos + tn + 1, R[nd[i]]) - pos - 1;
		assert(l <= r);
		mxl[r] = max(mxl[r], l);
	}
	for (int i = 1; i <= tn; i++) mxl[i] = max(mxl[i], mxl[i - 1]);
	ll res = 1e18;
	int l = 1, r = 1;
	q[l] = f[0] = 0;
	for (int i = 1; i <= tn; i++) {
		mxl[i] = max(mxl[i], mxl[i - 1]);
		int val = max(0, a[pos[i]] - V);
		ans += max(0, V - a[pos[i]]);
		while (l <= r && q[l] < mxl[i - 1]) l++;
		f[i] = val + f[q[l]];
		if (i >= mxl[tn]) res = min(res, f[i]);
		while (l <= r && f[q[r]] > f[i]) r--;
		q[++r] = i;
	}
	return res;
}
void Solve() {
	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", &L[i], &R[i], &X[i]);
	fill(lef + 1, lef + n + 1, 1);
	for (int i = 1; i <= m; i++) pl[i] = i;
	for (int i = 1; i <= n + 1; i++) fa[i] = i;
	sort(pl + 1, pl + m + 1, [](int x, int y) { return X[x] > X[y]; });
	ans = 0;
	for (int i = 1, j; i <= m; i = j + 1) {
		j = i;
		while (j < m && X[pl[j + 1]] == X[pl[i]]) j++;
		for (int k = i; k <= j; k++) {
			int id = pl[k];
			int o = gf(L[id]);
			if (o > R[id]) return cout << "-1\n", Clear();
		}
		tn = tq = 0;
		for (int k = i; k <= j; k++) {
			int id = pl[k];
			nd[++tq] = id;
			while (1) {
				int o = gf(L[id]);
				if (o > R[id]) break;
				lef[o] = X[id], fa[o] = o + 1, pos[++tn] = o;
			}
		}
		ans += Solve_v(X[pl[i]]);
	}
	cout << ans << '\n';
	Clear();
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) Solve();
}