#include<bits/stdc++.h>
using namespace std;
int n,m,r[1000002],d[1000002],s[1000002],t[1000002],sum[1000002];
bool pd(int x){
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=x;i++){
		for(int j=s[i];j<=t[i];j++){
			sum[j]+=d[j];
			if(sum[j]>r[j])return false;
		}
	}
	return true;
}
int main(){
	scanf("%d%d",&n,&m);
	int ri=m,le=1,mid=(m+1)/2;
	for(int i=1;i<=n;i++)scanf("%d",&r[i]);
	for(int i=1;i<=m;i++)scanf("%d%d%d",&d[i],&s[i],&t[i]);
	if(pd(m)){
		printf("0");
		return 0;
	}
	while(ri>le){
		mid=(ri+le)/2;
		if(pd(mid))le=mid+1;
		else ri=mid;
	}
	printf("-1\n%d",le);
	return 0;
}