#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair <int,int>
#define F first
#define S second
#define ever (;;)

const int N = 100100;

int n,m,a[N],par[N];
ll dis[N],inf = 1e18;
vector <ii> adj[N];
priority_queue < pair < ll , int > , vector < pair < ll , int > > , greater < pair < ll , int > > > q;

int get(int x) { return par[x] == x ? x : par[x] = get(par[x]); }

void mrg(int x,int y)
{
    x = get(x);
    y = get(y);

    if( x == y )
        return;

    if( x > y )
        swap(x,y);

    par[x] = y;
}

void dijkstra(int start)
{
    for(int i=1;i<=n;i++)
        dis[i] = inf;

    dis[start] = 0LL;
    q.push( { 0LL , start } );

    while( !q.empty() )
    {
        ll w = q.top().F;
        int u = q.top().S;

        q.pop();

        if( w != dis[u] )
            continue;

        for(auto &x:adj[u])
        {
            int l = x.F;
            int r = x.S;

            for(int i=l;i<=r;i=get(i))
            {
                if( u > i )
                {
                    if( dis[i] > w + a[u] - a[i] )
                    {
                        dis[i] = w + a[u] - a[i];
                        q.push( { dis[i] , i } );
                    }
                }
                else
                {
                    if( dis[i] > w )
                    {
                        dis[i] = w;
                        q.push( { dis[i] , i } );
                    }
                }

                mrg(i,i+1);

                i = get(i);
            }
        }
    }
}

int main()
{
    for(int i=0;i<N;i++)
        par[i] = i;

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    while( m-- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        adj[a].push_back( { b , c } );
    }

    dijkstra(1);

    for(int i=1;i<=n;i++)
        printf("%lld%c",(dis[i]==inf)?-1:2*dis[i]+a[i]-a[1],(i==n)?'\n':' ');
}