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

int n;
void dijkstra() {
	memset(dist, INF, sizeof dist);
	dist[1] = 0;
	set<pair<ll, int>> q;
	q.insert({ 0,1 });
	set<int> rem;
	for (int i = 1; i <= n; i++)
		rem.insert(i);
	while (q.size()) {
		int cur = q.begin()->second;
		ll w = q.begin()->first;
		q.erase(q.begin());
		rem.erase(cur);

		for (auto& interval : L[cur]) {
			int b = interval.first, c = interval.second;
			auto it = rem.lower_bound(b);
			while (it != rem.end() && *it <= c) {
				if (dist[*it] > dist[cur] + abs(a[cur] - a[*it])) {
					dist[*it] = dist[cur] + abs(a[cur] - a[*it]);
					q.erase({ dist[*it],*it });
					q.insert({ dist[*it],*it });
				}
				it++;
			}
		}
		
	}
}

int main() {
	run();
	int q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	while (q--) {
		int a, b, c;
		cin >> a >> b >> c;
		L[a].push_back({ b,c });
		/*
		if (max(b, a + 1) <= c)
			G[a].push_back({ max(b,a + 1),c });
		if (b <= min(c, a - 1))
			L[a].push_back({ b,min(c,a - 1) });*/
	}
	for (auto& it : G)
		merge_intervals(it);
	for (auto& it : L)
		merge_intervals(it);

	dijkstra();
	for (int i = 1; i <= n; i++) {
		if (dist[i] == INF)dist[i] = -1;
		cout << dist[i] << ' ';
	}
}