#include<cstdio>

#include<algorithm>

using namespace std;

int d[1000005],w[1000005],v[1000005],l[1000005];

long long F[100005][105];

int main(){

	int N,m,n=0;

	scanf("%d%d",&N,&m);

	for (int i=1; i<=m; i++) scanf("%d",&d[i]);

	for (int i=1; i<=N; i++){

		int W,V,L;

		scanf("%d%d%d",&W,&V,&L);

		if (1ll*W*L<=m){

			n++;

			w[n]=W;

			v[n]=V;

			l[n]=L;

		}

	}

	for (int i=0; i<=m; i++)

		for (int j=0; j<=n; j++)

			F[i][j]=-1ll<<60;

	F[0][0]=0;

	for (int i=0; i<=m; i++)

		for (int j=n; j>=0; j--)

			if (F[i][j]!=-1ll<<60){

				if (!j){

					for (int k=1; k<=n; k++)

						if (i+w[k]*l[k]<=m) F[i+w[k]*l[k]][k]=max(F[i+w[k]*l[k]][k],F[i][j]+1ll*v[k]*l[k]-d[i]);

				}

				else{

					if (i+w[j]<=m) F[i+w[j]][j]=max(F[i+w[j]][j],F[i][j]+v[j]);

					F[i][0]=max(F[i][0],F[i][j]);

				}

			}

	long long ans=0;

	for (int i=1; i<=m; i++){

		for (int j=0; j<=n; j++) ans=max(ans,F[i][j]);

		printf("%lld ",ans);

	}

	return 0;

}