#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m, cl[N], s[N], t[N];
long long c[N], f[N], h[N], d[N], temp;
bool check(int x) {
	for(int i = 1;i <= m;++i) f[i] = c[i];
	for(int i = 1;i <= x;++i)
		f[s[i]] -= d[i], f[t[i]+1] += d[i];
	long long k = 0;
	for(int i = 1;i <= n;++i) {
		k += f[i];
		if(k < 0) return true;
	}
	return false;
}
int main () {
	bool ok = true;
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;++i) scanf("%lld", cl+i), c[i] = cl[i]-cl[i-1], h[i] = c[i];
	for(int i = 1;i <= m;++i) scanf("%lld%d%d", d+i, s+i, t+i), h[s[i]] -= d[i], h[t[i]+1] += d[i];
	for(int i = 1;i <= n;++i) {
		temp += h[i];
		if(temp < 0) {ok = false; break;}
	}
	if(ok) printf("0"), exit(0);
	int l = 1, r = m, ans = m;
	while(l <= r) {
		int mid = (l+r) >> 1;
		if(check(mid)) {
			ans = mid;
			r = mid-1;
		}
		else l = mid+1;
	}
	printf("-1\n%d", ans);
	return 0;
}