#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];
bool cmp (qwq x, qwq y) {
    return x.v == y.v ? x.l < y.l : x.v < y.v;
}
multiset <int> s;
multiset <int>::iterator it;
int val[N];
vector<int> w[N];
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 (auto x : seg[x]) L[x.second] = max (L[x.second], x.first);
    for (auto x : seg[x]) lim = max (lim, x.first);
    int num = (int)w[x].size(), la = 0;
    ll ans = 1e18;
    u.insert (0);
    for (int i = 1; i <= num; ++i) {
        int now = w[x][i - 1];
        // printf ("%d %d\n", now, )
        f[i] = *u.begin() + abs (a[now] - val[x]);
        u.insert (f[i]);
        if (L[now] > 0) u.erase (0);
        while (la < num && w[x][la] < L[now]) {
            iu = u.find (f[la + 1]); u.erase (iu); ++la;
        }
        if (now >= lim) ans = min (ans, f[i]);
    }
    // printf ("hhh %lld\n", ans);
    u.clear();
    for (auto x : seg[x]) L[x.second] = 0;
    return ans;
}
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 + m + 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; i <= tot; ++i) ans += calc (i);
    printf ("%lld\n", ans);
}
signed main() {
    int T; read (T);
    for (int i = 1; i <= T && i <= 5; ++i) work ();
    return 0;
}