#include<bits/stdc++.h>
using namespace std;
long long n,m,r[10000000+10];
struct Dd{
    long long d,s,j;
};
Dd k[10000000+10];
bool check(long long x)
{
    long long t[1000000+10]={0};
    bool ok=true;
    for(long long i=1;i<=x;i++)
    {
        for(long long z=k[i].s;z<=k[i].j;z++){
            t[z]+=k[i].d;
            if(t[z]>r[z])
                {ok=false;break;}
        }
    }
    return ok;
}
int main(void)
{
    scanf("%lld %lld",&n,&m);
    for(long long i=1;i<=n;i++)
        scanf("%lld",&r[i]);
    
    for(long long i=1;i<=m;i++)
        scanf("%lld %lld %lld",&k[i].d,&k[i].s,&k[i].j);
    long long ls=1,rs=m;
    while(ls+1<rs)
    {
        long long mid=(ls+rs)/2;
        if(!check(mid))rs=mid;
        else ls=mid;
    }
    if(rs==m)
        cout<<0;
    else{
        cout<<-1<<endl;
        printf("%lld",rs);
    }
}