#include<bits/stdc++.h>
#include <stdio.h>
#include <algorithm>

#define all(x) x.begin(),x.end()
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define LL long long
#define LD long double
#define pb push_back
#define F first
#define S second


const double PI=3.1415926535897932384626433;
const int KL=1e6;
const LL MOD=1e9+7;


using namespace std;
/*
typedef complex<double> point;
#define x real()
#define y imag()
*/

LL q,n,a[KL],from[KL],to[KL],dis[KL];
vector <pair<LL,LL>> qu[KL];
set<pair<LL,LL>> s;
set<LL> ok;
bool vis[KL];
void dijkstra(){
    for(int i=1;i<=n;i++){
        dis[i]=1e17;
    }
    for(int i=2;i<=n;i++)ok.insert(i);
    dis[1]=0;
    s.insert({0,1});
    while(s.size()){
        LL node=(*s.begin()).S;
        s.erase(s.begin());
        if(vis[node])continue;
        vis[node]=1;
        for(auto v:qu[node]){
            LL l=v.F,r=v.S;
            auto it=ok.lower_bound(l);
            while(it!=ok.end() && *(it)<=r){
                LL u=*(it);
                ok.erase(u);
                if(dis[u]>dis[node]+abs(a[node]-a[u])){
                    s.erase({dis[u],u});
                    dis[u]=dis[node]+abs(a[node]-a[u]);
                    s.insert({dis[u],u});
                }
                it=ok.lower_bound(l);
            }
        }
    }
}

int main()
{

    scl(n);scl(q);
    for(int i=1;i<=n;i++){
        scl(a[i]);
    }
    while(q--){
        LL x,y,z;
        scl(x);scl(y);scl(z);
        qu[x].pb({y,z});
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        if(dis[i]==1e17){
            printf("-1 ");
        }
        else printf("%lld ",dis[i]);
    }printf("\n");


    return 0;
}