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

#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char * s, I L, I R) {
    cerr << "\e[1;32m[" << s << "] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

#define all(v) begin(v),end(v)

using ll = int64_t;

const ll INF = 1e18;

struct Segtree {
    using Tag = array<ll,2>;
    struct Node {
        ll best;
        ll mx[2];
        Node() : best(-INF), mx{-INF, -INF} {}
        Node(ll t_best, ll t_mx_0, ll t_mx_1) :
            best(t_best), mx{t_mx_0, t_mx_1} {}
    };

    static Node combine(const Node &lhs, const Node &rhs) {
        Node res;
        res.best = max(lhs.best, rhs.best);
        res.mx[0] = max(lhs.mx[0], rhs.mx[0]);
        res.mx[1] = max(lhs.mx[1], rhs.mx[1]);
        res.best = max(res.best, lhs.mx[0] + rhs.mx[1]);
        return res;
    }

    vector<Tag> lz;
    vector<Node> st;

    int n;
    void upd(int p, Tag t) {
        st[p].best += t[0] + t[1];
        st[p].mx[0] += t[0];
        st[p].mx[1] += t[1];
        if (p < n) {
            lz[p][0] += t[0];
            lz[p][1] += t[1];
        }
    }

    void pull(int p) {
        while (p >>= 1) {
            st[p] = combine(st[p << 1], st[p << 1 | 1]);
            st[p].best += lz[p][0] + lz[p][1];
            st[p].mx[0] += lz[p][0];
            st[p].mx[1] += lz[p][1];
        }
    }

    void push(int p) {
        for (int h = __lg(n) + 1; h >= 0; h--) {
            int i = p >> h;
            if (i == 1) continue;
            upd(i, lz[i >> 1]);
            upd(i ^ 1, lz[i >> 1]);
            lz[i >> 1] = { 0, 0 };
        }
    }

    Segtree(int t_n) {
        n = 1;
        while (n < t_n) n *= 2;
        debug(n, t_n);
        st.resize(n*2);
        lz.resize(n);
    }

    void init(vector<ll> &a, vector<ll> &b) {
        for (int i = 0; i < n; i++) {
            if (i < a.size())
                st[i + n] = { -INF, a[i], b[i] };
            else
                st[i + n] = Node();
        }
        for (int i = n - 1; i > 0; i--) {
            st[i] = combine(st[i << 1], st[i << 1 | 1]);
        }
    }

    void add(int l, int r, Tag t) {
        push(l + n), push(r - 1 + n);
        int tl = l, tr = r;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) upd(l++, t);
            if (r & 1) upd(--r, t);
        }
        pull(tl + n), pull(tr - 1 + n);
    }

    ll query(int l, int r) {
        push(l + n), push(r - 1 + n);

        Node resl, resr;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resl = combine(resl, st[l++]);
            if (r & 1) resr = combine(st[--r], resr);
        }
        return combine(resl, resr).best;
    }

    void dump() {
        debug("dump");
        vector<ll> f;
        vector<ll> s;
        vector<ll> t;
        for (int i = 0; i < n; i++) {
            push(i + n);
        }
        for (int i = 1; i < n * 2; i++) {
            f.push_back(st[i].mx[0]);
            s.push_back(st[i].mx[1]);
            t.push_back(st[i].best);
        }
        orange(all(f));
        orange(all(s));
        orange(all(t));
    }
};

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> a(N + 1);
    vector<ll> pre(N + 1);

    for (int i = 1; i <= N; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= N; i++) {
        pre[i] = pre[i - 1] + a[i];
    }

    vector<vector<tuple<int,int,int>>> evt(N + 2);

    for (int i = 0; i < M; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        if (c == 0)
            continue;

        evt[l].emplace_back(c, l - 1, r);
        evt[r + 1].emplace_back(-c, l - 1, r);
    }

    ll totc = 0;

    vector<ll> L(N + 1), R(N + 1);
    for (int i = 0; i <= N; i++) {
        L[i] = -pre[i];
        R[i] = pre[i];
    }

    Segtree sgt(N + 1);
    sgt.init(L, R);

    const auto query = [&](int ql, int qr) {
        ll ans = -1e18;
        for (int i = ql; i < N; i++) {
            for (int j = i + 1; j <= qr; j++) {
                ans = max(ans, R[j] + L[i]);
            }
        }
        return ans;
    };

    multiset<int> LS;
    multiset<int, greater<>> RS;

    for (int i = 1; i <= N; i++) {
        for (auto [c, l, r]: evt[i]) {
            if (c > 0) {
                LS.insert(l);
                RS.insert(r);
            } else {
                assert (LS.find(l) != LS.end());
                assert (RS.find(r) != RS.end());
                LS.erase(LS.find(l));
                RS.erase(RS.find(r));
            }
            totc += c;
            sgt.add(r, N + 1, { c, 0 });
            sgt.add(0, l + 1, { 0, c });
            sgt.dump();
            // for (int j = r; j <= N; j++)
            //     L[j] += c;
            // for (int j = 0; j <= l; j++)
            //     R[j] += c;
            // orange(all(L));
            // orange(all(R));
        }

        if (LS.empty()) {
            cout << 0 << (i==N ? '\n' : ' ');
        } else {
            int ql = *LS.begin();
            int qr = *RS.begin();
            debug(pre[qr] - pre[ql], sgt.query(ql, qr + 1), totc);
            // debug(query(ql, qr));
            ll ans = (pre[qr] - pre[ql])
                - max<ll>(0, sgt.query(ql, qr + 1) - totc);
            cout << ans << (i==N ? '\n' : ' ');
        }
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}