#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;
}
/*#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);
	rep(i,1,T) solve(i);
	return 0;
}*/

answer.code:314:5: error: redefinition of ‘int T’
  314 | int T,n,m;
      |     ^
answer.code:48:5: note: ‘int T’ previously declared here
   48 | int T,n,m;
      |     ^
answer.code:314:7: error: redefinition of ‘int n’
  314 | int T,n,m;
      |       ^
answer.code:48:7: note: ‘int n’ previously declared here
   48 | int T,n,m;
      |       ^
answer.code:314:9: error: redefinition of ‘int m’
  314 | int T,n,m;
      |         ^
answer.code:48:9: note: ‘int m’ previously declared here
   48 | int T,n,m;
      |         ^
answer.code:315:5: error: redefinition of ‘int a [100005]’
  315 | int a[100005];
      |     ^
answer.code:49:5: note: ‘int a [100005]’ previously declared here
   49 | int a[100005];
      |     ^
answer.code:316:4: error: redefinition of ‘long long int b [100005]’
  316 | ll b[100005];
      |    ^
answer.code:50:4: note: ‘long long int b [100005]’ previously declared here
   50 | ll b[100005];
      |    ^
answer.code:317:5: error: redefinition of ‘int _l [100005]’
  317 | int _l[100005],_r[100005],_w[100005];
      |     ^~
answer.code:51:5: note: ‘int _l [100005]’ previously declared here
   51 | int _l[100005],_r[100005],_w[100005];
      |     ^~
answer.code:317:16: error: redefinition of ‘int _r [100005]’
  317 | int _l[100005],_r[100005],_w[100005];
      |                ^~
answer.code:51:16: note: ‘int _r [100005]’ previously declared here
   51 | int _l[100005],_r[100005],_w[100005];
      |                ^~
answer.code:317:27: error: redefinition of ‘int _w [100005]’
  317 | int _l[100005],_r[100005],_w[100005];
      |                           ^~
answer.code:51:27: note: ‘int _w [100005]’ previously declared here
   51 | int _l[100005],_r[100005],_w[100005];
      |                           ^~
answer.code:318:14: error: redefinition of ‘std::vector<int> occ [2][100005]’
  318 | vector <int> occ[2][100005];
      |              ^~~
answer.code:52:14: note: ‘std::vector<int> occ [2][100005]’ previously declared here
   52 | vector <int> occ[2][100005];
      |              ^~~
answer.code:323:16: error: redefinition of ‘struct SEG1::node’
  323 |         struct node{
      |                ^~~~
answer.code:57:16: note: previous definition of ‘struct SEG1::node’
   57 |         struct node{
      |                ^~~~
answer.code:325:10: error: conflicting declaration ‘int SEG1::tree [400005]’
  325 |         }tree[400005];
      |          ^~~~
answer.code:59:10: note: previous declaration as ‘SEG1::node SEG1::tree [400005]’
   59 |         }tree[400005];
      |          ^~~~
answer.code:326:14: error: redefinition of ‘void SEG1::pushup(int)’
  326 |         void pushup(int rt){
      |              ^~~~~~
answer.code:60:14: note: ‘void SEG1::pushup(int)’ previously defined here
   60 |         void pushup(int rt){
      |              ^~~~~~
answer.code:330:14: error: redefinition of ‘void SEG1::build(int, int, int)’
  330 |         void build(int rt,int l,int r){
      |              ^~~~~
answer.code:64:14: note: ‘void SEG1::build(int, int, int)’ previously defined here
   64 |         void build(int rt,int l,int r){
      |              ^~~~~
answer.code:336:14: error: redefinition of ‘void SEG1::modify(int, int, int, int, int)’
  336 |         void modify(int rt,int l,int r,int pos,int C){
      |              ^~~~~~
answer.code:70:14: note: ‘void SEG1::modify(int, int, int, int, int)’ previously defined here
   70 |         void modify(int rt,int l,int r,int pos,int C){
      |              ^~~~~~
answer.code:350:16: error: redefinition of ‘struct SEG2::node’
  350 |         struct node{
      |                ^~~~
answer.code:84:16: note: previous definition of ‘struct SEG2::node’
   84 |         struct node{
      |                ^~~~
answer.code:352:10: error: conflicting declaration ‘int SEG2::tree [400005]’
  352 |         }tree[400005];
      |          ^~~~
answer.code:86:10: note: previous declaration as ‘SEG2::node SEG2::tree [400005]’
   86 |         }tree[400005];
      |          ^~~~
answer.code:353:14: error: redefinition of ‘void SEG2::pushup(int)’
  353 |         void pushup(int rt){
      |              ^~~~~~
answer.code:87:14: note: ‘void SEG2::pushup(int)’ previously defined here
   87 |         void pushup(int rt){
      |              ^~~~~~
answer.code:356:14: error: redefinition of ‘void SEG2::upd(int, long long int)’
  356 |         void upd(int rt,ll C){
      |              ^~~
answer.code:90:14: note: ‘void SEG2::upd(int, long long int)’ previously defined here
   90 |         void upd(int rt,ll C){
      |              ^~~
answer.code:360:14: error: redefinition of ‘void SEG2::build(int, int, int)’
  360 |         void build(int rt,int l,int r){
      |              ^~~~~
answer.code:94:14: note: ‘void SEG2::build(int, int, int)’ previously defined here
   94 |         void build(int rt,int l,int r){
      |              ^~~~~
answer.code:370:14: error: redefinition of ‘void SEG2::upload(int, int, int, int, int, long long int)’
  370 ...