#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int MAX = 5e5 + 10;
int n, m, a[MAX], T, fa[MAX];
struct tup
{
    int l, r, v;
    friend bool operator<(const tup &a, const tup &b)
    {
        if (a.v != b.v)
            return a.v > b.v;
        return a.r < b.r;
    }
} tu[MAX];
int Find(int x)
{
    return x == fa[x] ? x : (fa[x] = Find(fa[x]));
}
signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            fa[i] = i;
        }
        for (int i = 1; i <= m; i++)
        {
            cin >> tu[i].l >> tu[i].r >> tu[i].v;
        }
        sort(tu + 1, tu + m + 1);
        int sum = 0;
        for (int l = 1, r = 1; l <= m; r = l = r + 1)
        {
            while (r <= m && tu[r].v == tu[l].v)
            {
                r++;
            }
            r--;
            vector<int> v; // points to choose from
            for (int i = l; i <= r; i++)
            {
                int x = Find(tu[i].r);
                while (x >= tu[i].l)
                {
                    if (a[x] < tu[r].v)
                    {
                        sum += tu[r].v - a[x];
                        a[x] = tu[r].v;
                    }
                    v.push_back(x);
                    fa[x] = x - 1;
                    x = Find(x);
                }
            }
            deque<pii> Q;
            int L = 0, R = 0;
            auto j = v.begin();
            for (int i = l; i <= r; i++)
            {
                L = max(L, tu[i].l);
                while (Q.size() && Q.front().first < L)
                {
                    Q.pop_front();
                }
                for (; j < v.end() && *j <= tu[i].r; j++)
                {
                    if (*j < L)
                        continue;
                    while (Q.size() && Q.back().second > sum + a[*j] - tu[r].v)
                    {
                        Q.pop_back();
                    }
                    Q.push_back({*j, sum + a[*j] - tu[r].v});
                }
                if (Q.empty())
                {
                    cout << "-1" << endl;
                    goto fail;
                }
                else
                    sum = Q.front().second;
                R = tu[i].r;
            }
        }
        cout << sum << endl;
    fail:
    }
}