#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,n,m;
int a[100005];
ll b[100005];
int _l[100005],_r[100005],_w[100005];
vector <int> occ[2][100005];

#define ls (rt * 2)
#define rs (rt * 2 + 1)
namespace SEG1{//单点加,前缀 min
	struct node{
		ll sum,ans;
	}tree[400005];
	void pushup(int rt){
		tree[rt].sum = tree[ls].sum + tree[rs].sum;
		tree[rt].ans = min(tree[ls].ans,tree[ls].sum + tree[rs].ans);
	}
	void build(int rt,int l,int r){
		tree[rt].sum = tree[rt].ans = 0;
		if(l == r) return;
		int mid = (l + r) >> 1;
		build(ls,l,mid);build(rs,mid+1,r);
	}
	void modify(int rt,int l,int r,int pos,int C){
		if(l == r){
			tree[rt].sum += C;
			tree[rt].ans = min(tree[rt].sum,0ll);
			return;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid) modify(ls,l,mid,pos,C);
		else modify(rs,mid+1,r,pos,C);
		pushup(rt);
	}
}

namespace SEG2{//后缀加,全局定位最小值(left most)
	struct node{
		ll tag,Mn;
	}tree[400005];
	void pushup(int rt){
		tree[rt].Mn = min(tree[ls].Mn,tree[rs].Mn) + tree[rt].tag;
	}
	void upd(int rt,ll C){
		tree[rt].tag += C;
		tree[rt].Mn += C;
	}
	void build(int rt,int l,int r){
		tree[rt].tag = 0;
		if(l == r){
			tree[rt].Mn = b[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(ls,l,mid);build(rs,mid+1,r);
		pushup(rt);
	}
	void upload(int rt,int l,int r,int L,int R,ll C){
//		if(l == 1 && r == n) printf("upload [%d,%d] %lld\n",L,R,C);
		if(l == L && r == R){
			upd(rt,C);
			return;
		}
		int mid = (l + r) >> 1;
		if(R <= mid){
			upload(ls,l,mid,L,R,C);
		}else if(L > mid){
			upload(rs,mid+1,r,L,R,C);
		}else{
			upload(ls,l,mid,L,mid,C);
			upload(rs,mid+1,r,mid+1,R,C);
		}
		pushup(rt);
	}
	ll query(int rt,int l,int r,int L,int R,ll tot){
		if(L > R) return linf;
		if(l == L && r == R) return tree[rt].Mn + tot;
		int mid = (l + r) >> 1;
		tot += tree[rt].tag;
		if(R <= mid) return query(ls,l,mid,L,R,tot);
		else if(L > mid) return query(rs,mid+1,r,L,R,tot);
		else return min(query(ls,l,mid,L,mid,tot),query(rs,mid+1,r,mid+1,R,tot));
	}
	pair<int,ll> fnd(int rt,int l,int r,ll tot){
		if(l == r) return mkp(l,tree[rt].Mn + tot);
		int mid = (l + r) >> 1;
		tot += tree[rt].tag;
		if(tree[ls].Mn <= tree[rs].Mn) return fnd(ls,l,mid,tot);
		return fnd(rs,mid+1,r,tot);
	}
	inline int chk(){
		return tree[1].Mn >= 0;
	}
	void prt(int rt,int l,int r){
		printf("node %d [%d,%d] Mn %lld tag %lld\n",rt,l,r,tree[rt].Mn,tree[rt].tag);
	}
	void travel(int rt,int l,int r){
		if(l == r){
			prt(rt,l,r);
			return;
		}
		int mid = (l + r) >> 1;
		travel(ls,l,mid);travel(rs,mid+1,r);
		prt(rt,l,r);
	}
}

int rk[200005],idx[200005],lim[200005];
namespace SEG3{
	int c[200005];
	pii tree[800005];
	void build(int rt,int l,int r){
		tree[rt] = mkp(n + 1,0);
		if(l == r){
			c[l] = 0;
			return;
		}
		int mid = (l + r) >> 1;
		build(ls,l,mid);build(rs,mid+1,r);
	}
	void pushup(int rt){
		tree[rt] = min(tree[ls],tree[rs]);
	}
	void modify(int rt,int l,int r,int pos,int C){
		if(l == r){
			c[pos] += C;
			if(c[pos] > 0) tree[rt] = mkp(_l[idx[l]],l);
			else tree[rt] = mkp(n + 1,0);
			return;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid) modify(ls,l,mid,pos,C);
		else modify(rs,mid+1,r,pos,C);
		pushup(rt);
	} 
	pii query(int rt,int l,int r,int L,int R){
		if(l == L && r == R) return tree[rt];
		int mid = (l + r) >> 1;
		if(R <= mid) return query(ls,l,mid,L,R);
		else if(L > mid) return query(rs,mid+1,r,L,R);
		else return min(query(ls,l,mid,L,mid),query(rs,mid+1,r,mid+1,R));
	}
}

ll answer;
void maintain(){
//	printf("travel.\n");
//	SEG2::travel(1,1,n);
	while(!SEG2::chk()){
		pair<int,ll> temp = SEG2::fnd(1,1,n,0);
		int pos = temp.first;
//		printf("pos=%d val=%lld\n",pos,temp.second);
		int _id = SEG3::query(1,1,m,1,lim[pos]).second,id = idx[_id];//注意 id 是在 seg3 的位置
		int up = (int)min((ll)SEG3::c[_id],min(0ll,SEG2::query(1,1,n,1,_r[id] - 1,0)) - temp.second);
		SEG3::modify(1,1,m,_id,-up);
		SEG2::upload(1,1,n,_r[id],n,up);
		SEG1::modify(1,1,n,_l[id],up);
//		printf("discard %d %d current %d\n",id,up,SEG3::c[_id]);
		answer -= up;
	}
//	printf("fin\n");
}

void force(int pos,int C){//给 [pos,n] 的 limit 全部加 C
	SEG2::upload(1,1,n,pos,n,-C);
}

void solve(int testid){
	scanf("%d%d",&n,&m);
//	if(testid == 4) cerr << n << " " << m << endl;
	rep(i,1,n){
		scanf("%d",&a[i]);
		occ[0][i].clear();occ[1][i].clear();
		b[i] = b[i - 1] + a[i];
//		if(testid == 4) cerr << a[i] << " ";
	}
//	if(testid == 4) cerr << endl;
	rep(i,1,m){
		scanf("%d%d%d",&_l[i],&_r[i],&_w[i]);
		occ[0][_l[i]].eb(i);occ[1][_r[i]].eb(i);
//		if(testid == 4) cerr << _l[i] << " " << _r[i] << " " << _w[i] << endl; 
	}
	int _cur = 0;
	rep(i,1,n){
		for(int id:occ[1][i]){
			idx[++_cur] = id;
			rk[id] = _cur;
		}
		lim[i] = _cur;
	}

	answer = 0;
	SEG1::build(1,1,n);SEG2::build(1,1,n);SEG3::build(1,1,m);
	rep(i,1,n){
		if(i > 1){
			force(i - 1,a[i - 1]);
			maintain();
			answer += a[i - 1];
			SEG1::modify(1,1,n,i - 1,-a[i - 1]);
			for(int id:occ[1][i - 1]) SEG1::modify(1,1,n,_l[id],-_w[id]);
		}

		for(int id:occ[0][i]){
			SEG3::modify(1,1,m,rk[id],_w[id]);
			force(_r[id],_w[id]);
			answer += _w[id];
		}
		maintain();
		printf("%lld ",answer + SEG1::tree[1].ans);
	}
	printf("\n");
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d",&T);
	rep(i,1,T) solve(i);
	return 0;
}