//本道题是一道典型的差分和二分结合的题目——根据要求解的结果的特性进行二分
//差分暴力写法 O(mn)
//基本思路：设置一个空数组r2[n]来逐步存储前k个申请人在各个天中所需要的空教室数量，
//          每次遍历一个申请人相关的数据时，都去判断r2[n]是否有超出r[n]
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
int r[N], b[N], r2[N];
int n, m;
void chafen(int s, int t, int d)
{
    b[s] += d;
    b[t + 1] -= d;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &r[i]);

    //for(int i = 1; i <= n; i ++)
        //chafen(i, i, r[i]);

    for(int num = 1; num <= m; num ++)
    {
        int d, s, t;
        scanf("%d%d%d", &d, &s, &t);
        chafen(s, t, d);
        for(int i = 1; i <= n; i ++)
        {
            r2[i] = r2[i - 1] + b[i];
            //cout << r2[i] << " ";
            if(r[i] < r2[i])
            {
                puts("-1");
                printf("%d\n", num);
                return 0;
            }
        }
        //cout << endl;
    }
    puts("0");
    return 0;
}
//差分+二分写法 O(m+n)
//基本思路：由暴力的方法可知，我们设置了一个空数组r2[n]来逐步存储前k个申请人在各个天中所需要的空教室数量，
//          并且题目要求我们求解需要修改订单的申请人是哪一位，即在问我们第一个出现订购失败的人是谁(假设是第k个申请人)
//          因此，在第k个申请人之后的申请人都无法申请了，因为在第k个申请人时，已经出现r2[n]超出r[n]的情况，
//          所以，第k个申请人之后的申请人的订购需求只会使得r2[n]超出r[n]的情况更加严重；而在第k个申请人之前
//          做出申请的人都是可以订购成功的。因此根据申请人的编号是大于等于k，还是小于k，我们可以将第1到m个
//          申请人分成两个部分，一部分是可以申请的，另一部分是不可以申请的，所以本题可以通过“二分”的方法来解决。
//二分常规的做题顺序，基本上是1.先决定要二分的量（通常是题目中要求求解的结果），并考虑二分成的两部分区间有什么含义
//                            2.找出二分的判断条件，即怎么才能将要二分的量二分成两个部分
//                            3.但有的时候，题目会很简单，简单到你把各个变量之间的关系公式列出来就能发现该题目是可以二分的，
//                              比如1227.分巧克力，4956.冶炼金属
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL r[N], r2[N], s[N], t[N], d[N];
LL b[N];//差分数组
int n, m;
bool check(int mid)
{
    memset(b, 0, sizeof b);
    for(int i = 1; i <= mid; i ++)
    {
        b[s[i]] += d[i];
        b[t[i] + 1] -= d[i];
    }
    for(int i = 1; i <= n; i ++)
    {
        r2[i] = r2[i - 1] + b[i];
        //cout << r2[i] << " ";
        if(r2[i] > r[i]) return false;
    }
    return true;
}
int main()
{
    cin >> n >> m;//1, 6
    for(int i = 1; i <= n; i ++)
        scanf("%d", &r[i]);//r[1] = 1e9;

    for(int i = 1; i <= m; i ++)
        scanf("%d%d%d", &d[i], &s[i], &t[i]);//8e8, 1, 1

    //寻找第一个无法申请成功的申请人    
    int l = 1, r = m + 1;//1, 7
    while(l < r)
    {
        int mid = l + r >> 1;//4
        bool flag = check(mid);//检查编号为mid的申请人是否可以申请成功
        //cout << flag << endl;
        if(flag == 1) l = mid + 1;
        else r = mid;
    }
    if(r == m + 1) puts("0");
    else 
    {
        puts("-1");
        cout << r << endl;
    }
    return 0;
}