#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define fr first
#define sc second
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())
#define shuffle(a) shuffle(a.begin(), a.end(), rnd)

using namespace std;

using ll = long long;

#ifdef ONPC
mt19937 rnd(224);
mt19937_64 rndll(231);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rndll(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif


template<typename T>
void setmin(T &x, T y) {
    x = min(x, y);
}

template<typename T>
void setmax(T &x, T y) {
    x = max(x, y);
}

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

const int maxn = 2e5 + 100, inf = 1e9 + 100;

template<typename item>
struct segtree {
    vector<item> tree;
    int n = 1;

    segtree(int n = 1) : n(n) {
        tree.resize(1 << (__lg(max(1, n - 1)) + 2));
    }

    template<typename T>
    segtree(const vector<T> &v) {
        build(v);
    }

    template<typename T>
    void build(const vector<T> &v, int i, int l, int r) {
        if (l == r) {
            tree[i].init(v[l], l, r);
            return;
        }
        int m = (l + r) >> 1;
        build(v, i * 2 + 1, l, m);
        build(v, i * 2 + 2, m + 1, r);
        tree[i].update(tree[i * 2 + 1], tree[i * 2 + 2], l, r);
    }

    template<typename T>
    void build(const vector<T> &v) {
        n = v.size();
        tree.assign(1 << (__lg(max(1, n - 1)) + 2), item());
        build(v, 0, 0, n - 1);
    }

    item ask(int l, int r, int i, int vl, int vr) {
        if (vl != vr) {
            tree[i].push(tree[i * 2 + 1], tree[i * 2 + 2], vl, vr);
        }
        if (l == vl && r == vr) {
            return tree[i];
        }
        int m = (vl + vr) >> 1;
        if (r <= m) {
            return ask(l, r, i * 2 + 1, vl, m);
        } else if (m < l) {
            return ask(l, r, i * 2 + 2, m + 1, vr);
        } else {
            return item::merge(ask(l, m, i * 2 + 1, vl, m), ask(m + 1, r, i * 2 + 2, m + 1, vr), l, r);
        }
    }

    item ask(int l, int r) {
        l = max(l, 0);
        r = min(r, n - 1);
        if (l > r) return item();
        return ask(l, r, 0, 0, n - 1);
    }

    template<typename T>
    void set(int ind, const T &t) {
        static array<pair<int, int>, 30> st;
        int l = 0, r = n - 1, i = 0;
        int ptr = -1;
        while (l != r) {
            if (l != r) {
                tree[i].push(tree[i * 2 + 1], tree[i * 2 + 2], l, r);
            }
            st[++ptr] = {l, r};
            int m = (l + r) >> 1;
            if (ind <= m) {
                i = i * 2 + 1;
                r = m;
            } else {
                i = i * 2 + 2;
                l = m + 1;
            }
        }
        tree[i].init(t, l, r);
        while (i != 0) {
            i = (i - 1) / 2;
            tree[i].update(tree[i * 2 + 1], tree[i * 2 + 2], st[ptr].first, st[ptr].second);
            --ptr;
        }
    }

    template<typename Modifier>
    void modify(int l, int r, const Modifier &modifier, int i, int vl, int vr) {
        if (vl != vr) {
            tree[i].push(tree[i * 2 + 1], tree[i * 2 + 2], vl, vr);
        }
        if (l == vl && r == vr) {
            tree[i].modify(modifier, vl, vr);
            return;
        }
        int m = (vl + vr) >> 1;
        if (r <= m) {
            modify(l, r, modifier, i * 2 + 1, vl, m);
        } else if (m < l) {
            modify(l, r, modifier, i * 2 + 2, m + 1, vr);
        } else {
            modify(l, m, modifier, i * 2 + 1, vl, m);
            modify(m + 1, r, modifier, i * 2 + 2, m + 1, vr);
        }
        tree[i].update(tree[i * 2 + 1], tree[i * 2 + 2], vl, vr);
    }

    template<typename Modifier>
    void modify(int l, int r, const Modifier &modifier) {
        l = max(l, 0);
        r = min(r, n - 1);
        if (l > r) return;
        modify(l, r, modifier, 0, 0, n - 1);
    }
};


namespace item_max_value {
    struct item {
        ll w = 0, u = 0;
        int i;

        template<typename T>
        void init(const T &t, int l, int r) {
            i = l;
            w = t;
            u = 0;
        }

        void update(const item &first, const item &second, int l, int r) {
            if (make_pair(first.w, -first.i) > make_pair(second.w, -second.i))
                *this = first;
            else
                *this = second;
            u = 0;
        }

        static item merge(const item &first, const item &second, int l, int r) {
            item res;
            res.update(first, second, l, r);  // careful with different lengths
            return res;
        }

        template<typename Modifier>
        void modify(const Modifier &m, int l, int r) {
            w += m;
            u += m;
        }

        void push(item &first, item &second, int l, int r) {
            int m = (l + r) / 2;
            first.modify(u, l, m);
            second.modify(u, m + 1, r);
            u = 0;
        }
    };
}

namespace item_max_id {
    struct item {
        pair<int, int> w;

        template<typename T>
        void init(const T &t, int l, int r) {
            w = t;
        }

        void update(const item &first, const item &second, int l, int r) {
            w = min(first.w, second.w);
        }

        static item merge(const item &first, const item &second, int l, int r) {
            item res;
            res.update(first, second, l, r);  // careful with different lengths
            return res;
        }

        template<typename Modifier>
        void modify(const Modifier &m, int l, int r) {
        }

        void push(item &first, item &second, int l, int r) {
        }
    };

    // (l, i)
    set<pair<int, int>> q[maxn];
    segtree<item> t;

    pair<int, int> get(int i) {
        return q[i].empty() ? make_pair(inf, -1) : *q[i].begin();
    }

    void init(int n) {
        t.build(vector<pair<int, int>>(n, {inf, -1}));
        for (int i = 0; i < n; i++)
            q[i].clear();
    }

    int get(int l, int r) {
        return t.ask(l, r).w.sc;
    }

    void add(int i, pair<int, int> w) {
        auto old = get(i);
        q[i].insert(w);
        auto nw = get(i);
        if (old != nw)
            t.set(i, nw);
    }

    void rm(int i, pair<int, int> w) {
        auto old = get(i);
        q[i].erase(w);
        auto nw = get(i);
        if (old != nw)
            t.set(i, nw);
    }
}


void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> arr(n);
    for (int &i : arr)
        cin >> i;
    vector<pair<int, pair<int, int>>> segs(m);
    vector<int> left_val(m);
    vector<vector<int>> op(n), cl(n);
    for (int i = 0; i < m; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        l--;
        r--;
        segs[i] = {c, {l, r}};
        op[l].emplace_back(i);
        cl[r].emplace_back(i);
    }
    item_max_id::init(n);
    segtree<item_max_value::item> left, right;
    left.build(vector<int>(n, 0));
    right.build(vector<int>(n, 0));
    ll left_sum = 0, right_sum = 0;
    for (int i = 0; i < n; i++)
        right.modify(i, n - 1, -arr[i]);
    int job_done_times = 0;
    for (int i = 0; i < n; i++) {
        left.modify(0, i, -arr[i]);
        right.modify(i, n - 1, arr[i]);
        for (int ind : cl[i]) {
            int &c = segs[ind].fr;
            auto [l, r] = segs[ind].sc;
            if (l != r) {
                right_sum -= c;
                right.modify(r, n - 1, -c);
                item_max_id::rm(r, {l, ind});
            }
            left.modify(0, l, c);
            left_sum += c;
            left_val[ind] += c;
            c = 0;
        }
        for (int ind : op[i]) {
            int c = segs[ind].fr;
            auto [l, r] = segs[ind].sc;
            if (l == r)
                continue;
            item_max_id::add(r, {l, ind});
            right_sum += c;
            right.modify(r, n - 1, c);
        }

        // do the job
        {
            while (1) {
                auto max_val = right.ask(i, n - 1);
                if (max_val.w <= 0)
                    break;
                job_done_times++;
                int pos = max_val.i;
                assert(pos > i);
                int ind = item_max_id::get(i + 1, pos);
                int &c = segs[ind].fr;
                auto [l, r] = segs[ind].sc;
                ll max_left_val = right.ask(i, r - 1).w;
                assert(max_left_val >= 0);
                ll diff = max_val.w - max_left_val;
                assert(diff > 0);
                setmin(diff, (ll)c);
                right_sum -= diff;
                right.modify(r, n - 1, -diff);
                left_sum += diff;
                left.modify(0, l, diff);
                left_val[ind] += diff;
                c -= diff;
                if (c == 0)
                    item_max_id::rm(r, {l, ind});
            }
        }

        // calc ans
        {
            ll left_matching = left_sum - max(0ll, left.ask(0, i).w);
//            cerr << i << ' ' << left_matching << ' ' << right_sum << '\n';
            cout << left_matching + right_sum << ' ';
        }

        // close at i
        for (int ind : cl[i]) {
            int c = left_val[ind];
            auto [l, r] = segs[ind].sc;
            left_sum -= c;
            left.modify(0, l, -c);
        }

    }
    cout << '\n';
    cerr << job_done_times << '\n';
}
// check test counter

int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
    freopen("../a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ts;
    ts = 1;
    cin >> ts;
    for (int its = 1; its <= ts; its++)
        solve();
}