import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.Arrays;

public class Main {

    static int N = 1000010;
    static int n;
    static int m;
    static int[] r = new int[N];
    static int[] d = new int[N];
    static int[] s = new int[N];
    static int[] t = new int[N];
    static long[] ds = new long[N];


    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);

        String[] str2 = br.readLine().split(" ");

        for (int i = 1; i <= n; i++) {
            r[i] = Integer.parseInt(str2[i - 1]);
        }

        for (int i = 1; i <= m; i++) {
            String[] str3 = br.readLine().split(" ");
            d[i] = Integer.parseInt(str3[0]);
            s[i] = Integer.parseInt(str3[1]);
            t[i] = Integer.parseInt(str3[2]);
        }

        if (check(m)) {
            System.out.println(0);
        } else {
            System.out.println(-1);
            System.out.println(find());
        }
       
        br.close();
    }

    public static int find() {

        int l = 0;
        int r = m;

        while (l < r) {
            
            int mid = (l + r + 1) >> 1;

            if (check(mid)) l = mid;
            else r = mid - 1;
        }

        return r + 1;
    }

    public static boolean check(int mid) {
        
        Arrays.fill(ds, 0);
        for (int i = 1; i <= mid; i++) {
            foo( s[i], t[i], d[i]);
        }
        for (int i = 1; i <= n; i++) {
            ds[i] += ds[i - 1];
            if (ds[i] > r[i]) {
                return false;
            }
        }
        return true;
    }
    
    public static void foo(int l, int r, int k) {
        ds[l] += k;
        ds[r + 1] -= k;
    }
}

70分 TLE了
应该不是语音的限制吧，不知道哪里可以优化！

二分 + 前缀合 + 差分