#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];
int a[N], 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);
	}
}

namespace solverR {
	set<int> rem;
	vector<pair<int, int>> intervals[N];
	vector<int> add[N], remove[N];
	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 (b > c)continue;
			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;
		for (int i : rem) {
			for (auto& x : add[i])
				cur.insert({ dist[x] - a[x],x });
			add[i] = vector<int>();

			if (cur.size() && 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>();
		}
		for (auto& it : st)rem.erase(it);
		return st;
	}
};

namespace solverL {
	set<int> rem;
	vector<pair<int, int>> intervals[N];
	vector<int> add[N], remove[N];
	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 (b > c)continue;
			add[c].push_back(i);
			remove[b].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;
		for (auto it = rem.rbegin(); it != rem.rend(); it++) {
			int i = *it;

			for (auto& x : add[i])
				cur.insert({ dist[x] + a[x],x });
			add[i] = vector<int>();
			if (cur.size() && 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>();
		}
		for (auto& it : st)rem.erase(it);
		return st;
	}
};

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

	for (int i = 2; i <= n; i++) {
		solverR::rem.insert(i);
		solverL::rem.insert(i);
	}
	while (q--) {
		int a, b, c;
		cin >> a >> b >> c;
		if (b <= min(c, a - 1))
			solverL::intervals[a].push_back({ b,min(c,a - 1) });
		if (max(b, a + 1) <= c)
			solverR::intervals[a].push_back({ max(b,a + 1),c });
	}
	for (auto& it : solverR::intervals)
		merge_intervals(it);
	for (auto& it : solverL::intervals)
		merge_intervals(it);

	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] << ' ';
	}
}