#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

class Dsu {
  vector<int> p;
  int n;

 public:
  Dsu(int n) : n(n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  int find(int u) {
    return u == p[u] ? u : p[u] = find(p[u]);
  }

  void merge(int u, int v) {
    p[find(u)] = find(v);
  }
};

struct Edge {
  int l;
  int r;

  Edge(int l, int r) : l(l), r(r) {}
};

struct PQNode {
  int from;
  int l;
  int r;
  int minWeight;
  ll cost;

  PQNode(int from, int l, int r, int minWeight, ll cost)
      : from(from), l(l), r(r), minWeight(minWeight), cost(cost) {}

  bool operator<(const PQNode &rhs) const {
    return cost + minWeight > rhs.cost + rhs.minWeight;
  }
};

const ll INF = 1e18;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  vector<vector<Edge>> g(n);

  auto addEdge = [&](int s, int l, int r) {
    if (l > r) return;
    g[s].emplace_back(l, r);
  };

  for (int i = 0; i < q; ++i) {
    int s, l, r;
    cin >> s >> l >> r;
    --s, --l, --r;
    if (l <= s && s <= r) {
      addEdge(s, l, s - 1);
      addEdge(s, s + 1, r);
    } else {
      addEdge(s, l, r);
    }
  }

  auto getMinWeight = [&](int from, int l, int r) {
    if (from < l) return a[l] - a[from];
    if (from > r) return a[from] - a[r];
    assert(false);
  };

  priority_queue<PQNode> frontier;
  vector<ll> dist(n, INF);

  auto addNodes = [&](int from, ll cost) {
    for (Edge edge : g[from]) {
      frontier.emplace(from, edge.l, edge.r, getMinWeight(from, edge.l, edge.r), cost);
    }
  };

  frontier.emplace(0, 0, 0, 0, 0);
  Dsu nextLeft(n);
  Dsu nextRight(n);

  int cnt = 0;

  while (!frontier.empty()) {
    PQNode node = frontier.top();
    frontier.pop();

    ll upperCost = frontier.empty() ? INF : frontier.top().cost + frontier.top().minWeight;

    if (node.from <= node.l) {
      for (int i = nextRight.find(node.l); i <= node.r; i = nextRight.find(i + 1)) {
        if (i == n - 1 && dist[i] != INF) break;
        ll currentCost = node.cost + a[i] - a[node.from];
        assert(dist[i] == INF);

        if (currentCost > upperCost && cnt < 15 * (n + q)) {
          ++cnt;
          frontier.emplace(node.from, i, node.r, getMinWeight(node.from, i, node.r), node.cost);
          break;
        }

        if (i != n - 1) nextRight.merge(i, i + 1);
        if (i != 0) nextLeft.merge(i, i - 1);

        dist[i] = currentCost;
        addNodes(i, currentCost);

        if (i == n - 1) break;
      }

    } else {
      assert(node.from > node.r);

      for (int i = nextLeft.find(node.r); i >= node.l; i = nextLeft.find(i - 1)) {
        if (i == 0 && dist[i] != INF) break;
        ll currentCost = node.cost + a[node.from] - a[i];
        assert(dist[i] == INF);

        if (currentCost > upperCost && cnt < 15 * (n + q)) {
          ++cnt;
          frontier.emplace(node.from, node.l, i, getMinWeight(node.from, node.l, i), node.cost);
          break;
        }

        if (i != n - 1) nextRight.merge(i, i + 1);
        if (i != 0) nextLeft.merge(i, i - 1);

        dist[i] = currentCost;
        addNodes(i, currentCost);

        if (i == 0) break;
      }
    }
  }

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

  return 0;
}