#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 500010;
const int inf = 2e9;

int n, m, tot, a[maxn], mx[maxn], st[maxn][20], c[maxn], tlim[maxn], val[maxn];
ll dp[maxn];
vector<int> mvec[maxn], pos[maxn];
vector<pii> vec[maxn];
tuple<int, int, int> lim[maxn];
multiset<int> S;

int que(int l, int r) {
  int k = __lg(r - l + 1);
  return min(st[l][k], st[r - (1 << k) + 1][k]);
}

void work() {
  cin >> n >> m;
  rep (i, 1, n) cin >> a[i];
  rep (i, 1, n) mvec[i].clear();
  rep (i, 1, m) {
    int l, r, v;
    cin >> l >> r >> v, c[i] = v;
    mvec[l].emplace_back(v);
    mvec[r + 1].emplace_back(-v);
    lim[i] = make_tuple(l, r, v);
  }
  S.clear();
  rep (i, 1, n) {
    for (int x : mvec[i]) {
      if (x > 0) S.emplace(x);
      else S.erase(S.find(-x));
    }
    if (S.empty()) mx[i] = st[i][0] = inf;
    else mx[i] = st[i][0] = *prev(S.end());
  }
  rep (j, 1, 19) rep (i, 1, n - (1 << j) + 1) {
    st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  }
  rep (i, 1, m) {
    auto [l, r, v] = lim[i];
    if (que(l, r) != v) return cout << "-1\n", void();
  }
  sort(c + 1, c + m + 1), tot = unique(c + 1, c + m + 1) - c - 1;
  rep (i, 1, tot) vec[i].clear(), pos[i].clear();
  ll ans = 0;
  rep (i, 1, n) if (mx[i] != inf) {
    if (a[i] < mx[i]) ans += mx[i] - a[i], a[i] = mx[i];
    int w = lower_bound(c + 1, c + tot + 1, mx[i]) - c;
    pos[w].emplace_back(i);
  }
  rep (i, 1, m) {
    auto [l, r, v] = lim[i];
    v = lower_bound(c + 1, c + tot + 1, v) - c;
    vec[v].emplace_back(l, r);
  }
  rep (i, 1, tot) if (SZ(vec[i])) {
    int w = SZ(pos[i]);
    rep (j, 1, w) val[j] = a[pos[i][j - 1]] - c[i];
    rep (j, 1, w) tlim[i] = -1;
    pii qp = pii(w, w);
    for (auto &[l, r] : vec[i]) {
      l = lower_bound(ALL(pos[i]), l) - pos[i].begin() + 1;
      r = upper_bound(ALL(pos[i]), r) - pos[i].begin();
      if (l > r) return cout << "-1", void();
      chkmx(tlim[r + 1], l - 1), qp = pii(l, r);
    }
    rep (j, 1, w) chkmx(tlim[j], tlim[j - 1]);
    rep (j, 1, w) dp[i] = 1e18;
    set<ll> S;
    int pos = 0;
    S.emplace(0);
    rep (j, 1, w) {
      while (pos < tlim[j]) {
        S.erase(S.find(dp[pos]));
        pos++;
      }
      dp[j] = *S.begin() + val[j];
      S.emplace(dp[j]);
    }
    ll mn = 1e18;
    rep (j, qp.fi, qp.se) chkmn(mn, dp[j]);
    ans += mn;
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int t; cin >> t;
  while (t--) work();
}