#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<map>
#include<functional>
using namespace std;
using LL = long long;

struct DSU{
    vector<int> p;
    DSU(int n) : p(n + 1){
        iota(p.begin(), p.end(), 0);
    }

    int find(int x){
        return p[x] == x ? x : p[x] = find(p[x]);
    }

    bool same(int x, int y) { 
        return find(x) == find(y); 
    }

    bool merge(int x, int y){
        x = find(x), y = find(y);
        if (x == y) return false;
        p[y] = x;
        return true;
    }
};

const LL INF = 1e18;
struct Info {
    LL mn = INF;
};

Info operator+(const Info &a, const Info &b){
    return {min(a.mn, b.mn)};
}

using Tag = int;

void apply(Info &x, Tag &a, Tag f){
    if (f){
        a = 1;
        x.mn = INF;
    }
}

template<class Info, class Tag>
struct LazySegmentTree{
    int n;
    vector<Info> info;
    vector<Tag> tag;

    LazySegmentTree() {}

    LazySegmentTree(int n, Info _init = Info()){
        init(vector<Info>(n, _init));
    }

    LazySegmentTree(const vector<Info> &_init){
        init(_init);
    }

    void init(const vector<Info> &_init){
        n = (int)_init.size();
        info.assign((n << 2) + 1, Info());
        tag.assign((n << 2) + 1, Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r){
            if (l == r){
                info[p] = _init[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 0, n - 1);
    }
    
    void pull(int p){
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    
    void apply(int p, const Tag &v){
        ::apply(info[p], tag[p], v);
    }
    
    void push(int p){
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    
    void modify(int p, int l, int r, int x, const Info &v){
        if (l == r){
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x <= m){
            modify(2 * p, l, m, x, v);
        } 
        else{
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    
    void modify(int p, const Info &v){
        modify(1, 0, n - 1, p, v);
    }
    
    Info query(int p, int l, int r, int x, int y){
        if (l > y || r < x){
            return Info();
        }
        if (l >= x && r <= y){
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m + 1, r, x, y);
    }
    
    Info query(int l, int r){
        return query(1, 0, n - 1, l, r);
    }
    
    void modify(int p, int l, int r, int x, int y, const Tag &v){
        if (l > y || r < x){
            return;
        }
        if (l >= x && r <= y){
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        modify(2 * p, l, m, x, y, v);
        modify(2 * p + 1, m + 1, r, x, y, v);
        pull(p);
    }
    
    void modify(int l, int r, const Tag &v){
        return modify(1, 0, n - 1, l, r, v);
    }
};
int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++) cin >> a[i];
        map<int, vector<pair<int, int> > > mp;
        for(int i = 0; i < m; i++){
            int l, r, v;
            cin >> l >> r >> v;
            mp[-v].push_back({l, r});
        }
        DSU dsu(n + 1);
        bool ok = true;
        LL ans = 0;
        for(auto &[x, v] : mp){
            vector<int> p;
            for(auto [l, r] : v){
                for(int i = dsu.find(l); i <= r; i = dsu.find(i)){
                    p.push_back(i);
                    dsu.p[i] = i + 1;
                }
            }
            sort(p.begin(), p.end());
            const int m = p.size();
            vector<int> cost(m + 1);
            for(int i = 0; i < m; i++){
                if (a[p[i]] > -x){
                    cost[i + 1] = a[p[i]] + x;
                }
                else{
                    ans += -x - a[p[i]];
                }
            }

            auto get = [&](int x){
                return int(lower_bound(p.begin(), p.end(), x) - p.begin()) + 1;
            };

            vector<int> pos(m + 1, 1e9);
            for(auto [l, r] : v){
                l = get(l);
                r = get(r + 1) - 1;
                if (l > r){
                    ok = false;
                    break;
                }
                pos[r] = min(pos[r], l);
            }
            if (!ok) break;
            LazySegmentTree<Info, Tag> seg(m + 1);
            seg.modify(0, {0});
            for(int i = 1; i <= m; i++){
                LL dp = seg.query(0, m).mn + cost[i];
                seg.modify(i, {dp});
                if (pos[i] <= i){
                    seg.modify(0, pos[i] - 1, 1);
                }
            }
            ans += seg.query(0, m).mn;
        }
        if (!ok){
            cout << -1 << '\n';
            continue;
        }
        cout << ans << '\n';
    }

}