#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <vector>
#include <random>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define per(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << " \n"[_ == r]

using i64 = long long;

const i64 inf = 1e18;

const int N = 5e5 + 10;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + (c - 48);
  return x * f;
}

int n, m, a[N], bd[N], mx[N];
i64 f[N], pre[N], ans;
struct node {
  int l, r, k;
  node() {}
  friend bool operator < (node u, node v) {
    return u.k < v.k;
  }
} o[N];
map <int, vector <int>> pos;
map <int, vector <node>> lim;

int fa[N];
int get(int u) { return u == fa[u] ? u : fa[u] = get(fa[u]); }
void merge(int u, int v) { fa[get(v)] = get(u); }

void solve() {
  n = read(), m = read(), ans = 0;
  pos.clear(), lim.clear();
  rep(i, 1, n) a[i] = read();
  rep(i, 1, m) {
    o[i].l = read(), o[i].r = read(), o[i].k = read();
    lim[o[i].k].emplace_back(o[i]);
  }
  sort(o + 1, o + m + 1);
  rep(i, 1, n) fa[i] = i, bd[i] = -1;
  per(i, m, 1) {
    for (int p = o[i].r; (p = get(p)) >= o[i].l; merge(p - 1, p)) bd[p] = o[i].k;
  }
  rep(i, 1, n) if (~bd[i]) pos[bd[i]].emplace_back(i);
  // pa(bd, 1, n);
  for (auto [k, vec] : lim) {
    if (pos[k].empty()) {
      printf("-1\n");
      return;
    }
  }
  for (auto [k, vec] : pos) {
    // cout << "--- k = " << k << endl;
    int w = vec.size();
    // pv(w);
    // pa(vec, 0, w - 1);
    rep(i, 1, w) {
      mx[i] = 0, f[i] = inf;
      pre[i] = pre[i - 1] + max(0, k - a[vec[i - 1]]);
    }
    for (auto it : lim[k]) {
      int l = lower_bound(vec.begin(), vec.end(), it.l) - vec.begin() + 1;
      int r = lower_bound(vec.begin(), vec.end(), it.r) - vec.begin() + 1;
      if (l > r) {
        printf("-1\n");
        return;
      }
      // cout << "l, r = " << l << ' ' << r << endl;
      mx[r] = max(mx[r], l);
    }
    deque <int> q;
    q.push_back(0);
    rep(i, 1, w) {
      mx[i] = max(mx[i], mx[i - 1]);
      f[i] = f[i - 1];
      while (q.size() && q.front() < mx[i]) q.pop_front();
      if (q.size()) f[i] = min(f[i], f[q.front()] + pre[i - 1] - pre[q.front()]);
      f[i] += abs(k - a[vec[i - 1]]);
      while (q.size() && f[q.back()] >= f[i]) q.pop_back();
      q.push_back(i);
    }
    // pa(mx, 1, w);
    // pa(f, 1, w);
    // pa(g, 1, w);
    i64 res = inf;
    rep(i, mx[w], w) res = min(res, f[i]);
    ans += res;
  }
  printf("%lld\n", ans);
}

int main() {
  for (int tc = read(); tc; --tc) solve();
  return 0;
}