#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
void read (int &x) {
    char ch = getchar(); x =0 ; while (!isdigit(ch)) ch =getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 5e5 + 5;
int n, m, a[N];
vector<int> del[N], add[N];
#define pb push_back
struct qwq { int l, r, v; } b[N];
multiset <int> s;
multiset <int>::iterator it;
int val[N];
vector<int> w[N]; vector<int>::iterator iw;
vector<pair<int, int> > seg[N]; 
#define ll long long
int L[N];
multiset<ll> u;  ll f[N];
multiset<ll>::iterator iu;
ll calc (int x) {
    int lim = 0;
    // printf ("666 %d\n", val[x]);
    // for (auto x : seg[x]) printf ("%d %d\n", x.first, x.second);
    // for (int y : w[x]) printf ("%d ", y); puts ("");
    for (int y : w[x]) L[y] = 0;
    for (auto i : seg[x]) {
        int l = i.first, r = i.second;
        iw = upper_bound (w[x].begin(), w[x].end(), r);
        if (iw == w[x].begin()) return -1;
        --iw; if (*iw < l) return -1;
        // printf ("ok %d %d\n", x, *iw);
        L[*iw] = max (L[*iw], l);
        lim = max (lim, l);
    }
    int num = (int)w[x].size(), la = 0, tag = 1;
    ll ans = 1e18;
    u.clear(); u.insert (0);
    for (int i = 1; i <= num; ++i) {
        int now = w[x][i - 1];
        // printf ("%d %d\n", now, )
        if ((int)u.size() == 0) return -1;
        f[i] = *u.begin() + abs (a[now] - val[x]);
        // printf ("123 %d %lld\n", i, f[i]);
        u.insert (f[i]);
        if (a[now] < val[x]) {
            u.clear (), tag = 0; u.insert (f[i]); la = i - 1;
        } else {
            if (tag && L[now]) iu = u.find (0), u.erase (iu), tag = 0;
            while (la < num && w[x][la] < L[now]) {
                iu = u.find (f[la + 1]); u.erase (iu); ++la;
            }      
        }
    }
    if ((int)u.size() == 0) return -1;
    // printf ("hhh %lld\n", ans);
    return *u.begin();
}
void work () {
    read (n), read (m);
    for (int i = 1; i <= n; ++i) read (a[i]);
    for (int i = 1; i <= n; ++i) del[i].clear(), add[i].clear();
    for (int i = 1, l, r, v; i <= m; ++i) {
        read (l), read (r), read (v);
        b[i] = (qwq){l, r, v}; val[i] = v;
    }
    sort (val + 1, val + m + 1);
    int tot = unique (val + 1, val + m + 1) - val - 1;
    for (int i = 1; i <= tot; ++i) seg[i].clear(), w[i].clear();
    for (int i = 1; i <= m; ++i) {
        int v = lower_bound (val + 1, val + tot + 1, b[i].v) - val;
        b[i].v = v;
        add[b[i].l].pb (v), del[b[i].r + 1].pb (v);
        seg[v].push_back (make_pair (b[i].l, b[i].r));
    }
    s.clear ();
    for (int i = 1; i <= n; ++i) {
        for (int x : add[i]) s.insert (-x);
        for (int x : del[i]) it = s.find (-x), s.erase (it);
        if ((int)s.size() == 0) continue;
        int now = *s.begin();
        w[-now].push_back (i);
    }   
    long long ans = 0;
    for (int i = 1, t = 0; i <= tot; ++i) {
        t = calc (i); ans += t; if (t == -1) return (void)puts("-1");
    }
    printf ("%lld\n", ans);
}
signed main() {
    int T; read (T);
    while (T--) work ();
    return 0;
}