#include<bits/stdc++.h>
#define MAXN 100010
#define ll long long
using namespace std;

ll n,m;
ll r[MAXN],d[MAXN],s[MAXN],t[MAXN],diff[MAXN];

bool check(int k)
{
    memset(diff,0,sizeof(diff));
	for(int i=1;i<=k;++i)
	{
		diff[s[i]]+=d[i];
		diff[t[i]+1]-=d[i];
	}
	ll sum=0;
	for(int i=1;i<=n;++i)
	{
		sum+=diff[i];
		if(sum>r[i]) return 0;
	}
	return 1;
}

int main()
{
	freopen("classrooms.in", "r", stdin);
	freopen("classrooms.out", "w", stdout);
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>r[i];
	for (int i=1;i<=m;i++) cin>>d[i]>>s[i]>>t[i];
	if(check(m)) 
	{
		cout<<0;
		return 0;
	}
	ll l=1,r=m,ans=0;
	while(l<=r) 
	{
		int mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else 
		{
			ans=mid;
			r=mid-1;
		}
	}
	cout<<-1<<endl<<ans<<endl;
	return 0;
}