#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#define ll long long
#define gys mylove
using namespace std;
const int maxn=1000000+10;
int d,s,t;
int n,m,pos;
ll a[maxn],b[maxn],sum;
int rd[maxn],rs[maxn],rt[maxn];
inline void in(int &x)
{
    x=0;int f=1;char t=getchar();
    while(!isdigit(t)){if(t=='-')f=-1;t=getchar();}
    while(isdigit(t)){x=x*10+t-48;t=getchar();}
    x*=f;
}
inline void lin(ll &x)
{
    x=0;int f=1;char t=getchar();
    while(!isdigit(t)){if(t=='-')f=-1;t=getchar();}
    while(isdigit(t)){x=x*10+t-48;t=getchar();}
    x*=f;
}
inline int div(int l,int r){
	int mid;
	while(l<=r){
		mid=(l+r)>>1;
		for(int i=1;i<=mid;i++){
			b[rs[i]]+=rd[i];
			b[rt[i]+1]-=rd[i];
		}
		for(int i=1;i<=n;i++){
			sum+=b[i];
			if(sum>a[i]){
				r=mid-1;break;
			}
			else pos++;
		}
		if(pos==n) l=mid+1;
		sum=0;pos=0;
		memset(b,0,sizeof(b));
	}
	if(l==m+1) printf("0");
	else printf("-1\n%d",l);
}
inline void work(){
	in(n);in(m);
	for(int i=1;i<=n;i++) lin(a[i]);
	for(int i=1;i<=m;i++){
		in(rd[i]);in(rs[i]);in(rt[i]);
	}
	div(0,m);
}
inline int Main(){
	freopen("classrooms.in","r",stdin);
	freopen("classrooms.out","w",stdout);
	work();
	return 0;
}
int main(){;}
int gys=Main();