#define  _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <random>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()* ((uint64_t) new char | 1));
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[]{ -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[]{ 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
	return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
	return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#else
#endif
}

const int N = 1e5 + 9;
ll dist[N];
void merge_intervals(vector<pair<int, int>>& e) {
	sort(all(e));
	vector<pair<int, int>> tmp = move(e);
	for (auto& it : tmp) {
		if (e.empty() || e.back().second < it.first)
			e.push_back(it);
		else
			e.back().second = max(e.back().second, it.second);
	}
}


template<typename T>
struct solver {
	vector<ll> a;
	set<int, T> rem, newNode;
	vector<vector<pair<int, int>>> intervals;
	vector<vector<int>> add, remove;

	solver() {}
	solver(int n) :
		intervals(n + 1), add(n + 2), remove(n + 2) {
		for (int i = 2; i <= n; i++)
			rem.insert(i);
	}
	void add_node_intervals(int i) {
		for (auto& intr : intervals[i]) {
			int b = intr.first, c = intr.second;
			auto it = rem.lower_bound(b);
			if (it != rem.end())b = *it;
			else continue;

			it = rem.upper_bound(c);
			if (it != rem.begin())c = *(--it);
			else continue;

			if (T()(c, b))continue;

			newNode.insert(b);
			add[b].push_back(i);
			remove[c].push_back(i);
		}
	}
	set<int> solve(set<int>& st) {
		if (st.empty())return st;
		for (int i : st)
			add_node_intervals(i);
		st.clear();
		set<pair<ll, int>> cur;
		auto it = rem.begin();
		while (it != rem.end()) {
			int i = *it;
			for (auto& x : add[i])
				cur.insert({ dist[x] - a[x],x });
			add[i] = vector<int>();

			if (newNode.size() && *newNode.begin() == i)
				newNode.erase(*newNode.begin());
			if (cur.empty()) {
				if (newNode.empty())break;
				it = rem.lower_bound(*newNode.begin());
				continue;
			}
			if (dist[i] > cur.begin()->first + a[i]) {
				dist[i] = cur.begin()->first + a[i];
				add_node_intervals(i);
				st.insert(i);
			}
			for (auto& x : remove[i])
				cur.erase({ dist[x] - a[x],x });
			remove[i] = vector<int>();
			it++;
		}
		for (auto& it : st)rem.erase(it);
		return st;
	}
};

int main() {
	run();
	int n, q;
	cin >> n >> q;
	vector<ll> a(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	solver<less<int>> solverR(n);
	solver<greater<int>> solverL(n);
	solverR.a = solverL.a = a;
	for (auto& it : solverL.a)it *= -1;
	while (q--) {
		int a, b, c;
		cin >> a >> b >> c;
		if (max(b, a + 1) <= c)
			solverR.intervals[a].push_back({ max(b,a + 1),c });
		if (b <= min(c, a - 1))
			solverL.intervals[a].push_back({ b,min(c,a - 1) });
	}
	for (auto& it : solverR.intervals)
		merge_intervals(it);
	for (auto& it : solverL.intervals) {
		merge_intervals(it);
		for (auto& p : it)swap(p.first, p.second);
	}

	memset(dist, INF, sizeof dist);
	dist[1] = 0;
	set<int> st = { 1 };
	while (st.size()) {
		st = solverR.solve(st);
		st = solverL.solve(st);
	}
	for (int i = 1; i <= n; i++) {
		if (dist[i] == INF)dist[i] = -1;
		cout << dist[i] << ' ';
	}
}