/*
二分查找申请人编号：对于每个查询订单mid创建一个新的差分，然后减去1-mid的各个的值，再前缀和查看有没有小于0的
然后二分找到不能满足的订单，不能满足是指满足第一个、第二个、、直到不能满足这一个，
那么往后都是不能满足的，往前都是能满足的，由此来二分查找，

*/
import java.io.*;
public class Main{
    static int N=1000010,n,m;
    static int L[]=new int[N];
    static int R[]=new int[N];
    static int w[]=new int[N];
    static int r[]=new int[N];
    static long a[]=new long[N];
    public static void main(String[] args) throws Exception {
        BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
        String a2[]=sc.readLine().split(" ");
        n=Integer.parseInt(a2[0]);;
        m=Integer.parseInt(a2[1]);
        String[] ak=sc.readLine().split(" ");
        for(int i=1;i<=n;i++) {
            r[i]=Integer.parseInt(ak[i-1]);
        }
        for(int i=1;i<=m;i++){ 
            String s[]=sc.readLine().split(" ");
            w[i]=Integer.parseInt(s[0]);
            L[i]=Integer.parseInt(s[1]);
            R[i]=Integer.parseInt(s[2]);
        }
        if(insert(m)){ //1-m都可以满足就均可满足,否则二分找不能满足的
           System.out.println(0);
           return ;
        }  
        int l=1,r=m;
        while(l<r){ //能满足1-mid的订单才往右找不能满足的，二分缩小范围，
            int mid=l+r>>1;
            if(!insert(mid)) r=mid;
            else l=mid+1;
        }
        System.out.printf("%d\n%d",-1,r);
    }
    static boolean insert(int mid){ 
        for(int i=1;i<=n;i++) a[i]=r[i]-r[i-1];  //因为是查找不是遍历，所以每次创建一个新的差分
        for(int i=1;i<=mid;i++){
            a[L[i]]-=w[i];
            a[R[i]+1]+=w[i];
        }
        for(int i=1;i<=n;i++){
            a[i]+=a[i-1];
            if(a[i]<0) return false;
        }
        return true;
    }
}