#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
long long r[N],d[N],s[N],t[N],delt[N],need[N],n,m;
bool Is_ok(int x)
{
	for(int i=1;i<=n+1;i++) delt[i]=r[i]-r[i-1];
	for(int i=1;i<=x-1;i++)
	{
		delt[s[i]]-=d[i];
		delt[t[i]+1]+=d[i];
	}
	for(int i=1;i<=n;i++)
	{
		delt[i]=delt[i-1]+delt[i];
	}
	for(int i=s[x];i<=t[x];i++)
	{
		if(delt[i]<d[x]) return 0;
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>r[i];
	for(int j=1;j<=m;j++) 
	{
		cin>>d[j]>>s[j]>>t[j];
	}
	int _l=1,_r=m;
	if(Is_ok(_r)) 
	{
		cout<<"0";
		return 0;
	}
	while(_l<_r)
	{
		int mid=(_l+_r)/2;
		if(Is_ok(mid)) _l=mid+1;
		else _r=mid;
	}
	cout<<"-1"<<endl<<_l;
}