#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
/*
 * line : 原数列
 * l, r, d, : 题目要求的 对于每个区间的左端点 右端点 值
 * change : 差分数组 
 * 题解：对采用的订单数进行二分，每次用差分数组优化处理当天需要的教室数并与当天可对外借出的教室数比较检验。-Megumin
 */

//不知都为什么会无限循环； 
int line[1000010], l[1000010], r[1000010], d[1000010], change[1000010];
int n, m;
 
int check(int x)
{
	int count= 0;
	memset(change,0,sizeof(change));
	for(int i = 1;i<=n;i++)
	{
		change[i] = line[i] - line[i-1];
	}
	for (int i = 1; i <= x; i++) //这里使用差分，符号与原差分相反，是由于前一个人借走教室，相当于在原有的数量加上一个负数，所以将符号取反。
	{
		change[l[i]] -= d[i];
        change[r[i]+ 1] += d[i];
		//obj 1用差分数组对前x个操作进行处理 
	}

	for (int i = 1; i <= n; i++) 
	{
		line[i] = line[i-1] + change[i];
	}
		//obj 2抹平差分数组 
	for (int i = 1; i <= n; i++) 
		if(line[i] < 0)
		{
			return 0;
		}
		//obj 3什么情况下是发生了问题？ 
	return 1;
}

int main()
{
	scanf("%d %d", &n, &m);

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

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

     printf("%d\n",check(m));
	if(check(m))//obj 4什么情况是全都可以成立 
	{
		printf("0");
		return 0;
	}


    //m为订单的数量；
	int left = 1, right = m, mid;
	while(left<=right)
	{
		mid = (left + right) >> 1;
		if(check(mid))//obj 5如果成功订单的数量可以往上加；
			left = mid + 1;
		else
			right = mid;
	}
	printf("-1\n");
	printf("%d", left);

	return 0;
}