#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;
bool vis[KL];
void dijkstra(){
    for(int i=1;i<=n;i++){
        dis[i]=1e17;
    }
    dis[1]=0;
    s.insert({0,1});
    while(s.size()){
        LL node=(*s.begin()).S;
        LL sum=(*s.begin()).F;
        s.erase(s.begin());
        ///cout<<node<<" "<<sum<<endl;
        if(vis[node])continue;
        vis[node]=1;
        for(auto v:qu[node]){
            LL l=v.F,r=v.S;
            LL fnl=l;
            for(LL i=l;i<=r;i=to[i]){
                fnl=i;
                if(i==node)continue;
                if(dis[i]>abs(a[i]-a[node])+sum){
                    ///cout<<node<<" "<<i<<endl;
                    dis[i]=abs(a[i]-a[node])+sum;
                    s.insert({dis[i],i});
                }
            }
            fnl=to[fnl];
            LL first=from[l];
            vector <LL> vec;
            for(LL i=l;i<=r;i=to[i]){
                vec.pb(i);
            }
            for(auto v:vec){
                to[v]=fnl;
                from[v]=first;
            }
            to[first]=fnl;
            from[fnl]=first;
            vec.clear();
        }
    }
}

int main()
{

    scl(n);scl(q);
    for(int i=0;i<=n+1;i++){
        to[i]=i+1;
        from[i]=i-1;
    }
    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;
}