#include <bits/stdc++.h>
using namespace std;

int main() {
    static const int maxn = 500010;
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        static int a[maxn];
        for (int i = 1; i <= n; i++) scanf("%d", a + i);
        struct seg {
            int l, r, v;
        };
        static seg s[maxn];
        for (int i = 1; i <= m; i++) scanf("%d %d %d", &s[i].l, &s[i].r, &s[i].v);
        sort(s + 1, s + m + 1, [](const seg x, const seg y) { return x.v > y.v; });
        long long ans = 0;
        static int fa[maxn];
        for (int i = 1; i <= n + 1; i++) fa[i] = i;
        function<int(int)> find = [&find](const int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); };
        for (int i = 1; i <= m; i++) {
            int j = i;
            vector<int> vec;
            while (j <= m && s[j].v == s[i].v) {
                int u = find(s[j].l);
                while (u <= s[j].r) vec.push_back(u), fa[u] = find(u + 1), u = find(u);
                j++;
            }
            sort(vec.begin(), vec.end());
            static int L[maxn];
            for (int i = 0; i < vec.size(); i++) L[i] = -1;
            int mxL = -1;
            for (int p = i; p < j; p++) {
                int l = lower_bound(vec.begin(), vec.end(), s[p].l) - vec.begin();
                int r = upper_bound(vec.begin(), vec.end(), s[p].r) - vec.begin() - 1;
                L[r] = max(L[r], l), mxL = max(mxL, l);
                if (l > r) {
                    ans = -1;
                    break;
                }
            }
            if (ans == -1)
                break;
            for (int i = 1; i < vec.size(); i++) L[i] = max(L[i], L[i - 1]);
            int V = s[i].v;
            long long mi = LLONG_MAX;
            static long long dp[maxn];
            for (int p : vec) ans += max(0, V - a[p]);
            struct BIT {
                int n;
                long long a[maxn];
                inline void init(const int n) {
                    this->n = n;
                    for (int i = 1; i <= n; i++) a[i] = LLONG_MAX >> 1;
                    return;
                }
                inline void insert(int p, long long x) {
                    for (int i = p + 1; i <= n; i += i & -i) a[i] = min(a[i], x);
                }
                inline long long query(int p) {
                    long long ret = LLONG_MAX >> 1;
                    for (int i = p + 1; i; i -= i & -i) ret = min(ret, a[i]);
                    return ret;
                }
            };
            static BIT t;
            t.init(vec.size());
            for (int i = 0; i < vec.size(); i++) {
                int D = a[vec[i]] > V ? a[vec[i]] - V : 0;
                dp[i] = !i || L[i - 1] == -1 ? 0 : t.query(L[i - 1]);
                t.insert(i, dp[i] += D);
                if (i >= mxL)
                    mi = min(mi, dp[i]);
            }
            ans += mi, i = j - 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}