#include<bits/stdc++.h>
using namespace std;
int n, m, ans = INT_MAX;
int r[1000001], c[1000001], now;
int d[1000001], s[1000001], t[1000001];
bool check(int mid) {
	int sum = 0;
	if (now > mid) {
		for (int i = mid + 1; i <= now; i++) {
			c[s[i]] -= d[i];
			c[t[i] + 1] += d[i];
		}
	} else {
		for (int i = now + 1; i <= mid; i++) {
			c[s[i]] += d[i];
			c[t[i] + 1] -= d[i];
		}
	}
	now = mid;
	for (int i = 1; i <= n; i++) {
		sum += c[i];
		if (sum > r[i]) {
			return true;
		}
	}
	return false;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> r[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> d[i] >> s[i] >> t[i];
	}
	int l = 1, r = m, mid;
	while (l <= r) {
		if (l <= r) {
			mid = (l + r) / 2;
			if (check(mid)) {
				ans = min(ans, mid);
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
	}
	if (ans != INT_MAX) {
		cout << -1 << endl;
		cout << ans << endl;
	} else {
		cout << 0;
	}
	return 0;
}