#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <unordered_map>
//#include"testlib.h"
#define endl '\n'
#define all(v) v.begin(),v.end()
#define allr(s) s.rbegin(),s.rend()
#define RT(s) return cout<<s,0
#define sz(s)    (int)(s.size())
//#define PI acos(-1)
#define EPS 1e-8
#define watch(x) cout << (#x)<<" = "<<x<<endl
#define mk(x, y) make_pair(x, y)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void file() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
	//freopen("gcd.in", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
}

void fast() {
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
}
const int N = 1e5 + 3;
vector<ii> adjL[N];
int a[N], n;
ll d[N];
int main() {
	file();
	fast();
	int q; cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	while (q--) {
		int u, b, c; cin >> u >> b >> c;
		adjL[u].push_back({ b, c });
	}
	for (int i = 1; i <= n; i++)
		d[i] = LLONG_MAX;
	set<int> nodes;
	for (int i = 2; i <= n; i++)
		nodes.insert(i);
	deque<int> st, tmp;
	auto add_up = [&](int u) {
		for (auto& ra : adjL[u]) {
			while (true) {
				auto it = nodes.lower_bound(max(u + 1, ra.first));
				if (it == nodes.end() || *it > ra.second) break;
				int v = *it;
				nodes.erase(it);
				d[v] = min(d[v], d[u] + abs(a[u] - a[v]));
				tmp.push_back(v);
				st.push_back(v);
			}
		}
	};
	auto add_down = [&](int u) {
		for (auto& ra : adjL[u]) {
			while (true) {
				auto it = nodes.upper_bound(min(u - 1, ra.second));
				if (it == nodes.begin()) break;
				it--;
				int v = *it;
				if (v < ra.first) break;
				nodes.erase(it);
				d[v] = min(d[v], d[u] + abs(a[u] - a[v]));
				tmp.push_back(v);
				st.push_back(v);
			}
		}
	};
	st.push_back(1);
	d[1] = 0;
	for (int bit = 0; sz(st); bit = (bit + 1) & 1) {
		sort(all(st));
		if (bit)
			reverse(all(st));
		while (sz(st)) {
			int num = st.back();
			st.pop_back();
			//watch(num);
			if (!bit) add_up(num);
			else add_down(num);
			if (!bit) tmp.push_back(num);
		}
		st = tmp;
		tmp.clear();
	}
	for (int i = 1; i <= n; i++)
		cout << (d[i] == LLONG_MAX ? -1 : d[i]) << ' ';
	cout << endl;
	return 0;
}