#include <iostream>
#include <fstream>
#include <vector>
#define N 51000
#define M 251000
#define MAXINT 60000000


using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

vector <int> a[N];
int minim[N],dr[M],poz[N],h[N];
short cost[M];

int ok[M];

inline void swap(int a,int b)
{
    int c=h[a];
    h[a]=h[b];
    h[b]=c;
    poz[h[a]]=a;
    poz[h[b]]=b;
}

inline void urca(int p)
{
    while(p!=1 && minim[h[p]]<minim[h[p/2]])
    {
        swap(p,p/2);
        p=p/2;
    }
}

inline void coboara(int p)
{
    int ps=p;
    if(p*2<=h[0] && minim[h[ps]]>minim[h[p*2]])
        ps=p*2;
    if(p*2+1<=h[0] && minim[h[ps]]>minim[h[p*2+1]])
        ps=p*2+1;
    if(ps!=p)
    {
        swap(ps,p);
        coboara(ps);
    }
}

inline void scoate(int x)
{
    h[poz[x]]=h[h[0]];
    poz[h[h[0]]]=poz[x];
    h[0]--;
    urca(poz[x]);
    coboara(poz[x]);
}

int main()
{
    int n,m,i,x,j;
    in>>n>>m;
    for(i=1;i<=m;++i)
    {
         in>>x>>dr[i]>>cost[i];
         a[x].push_back(i);
    }
    for(i=2;i<=n;i++)
        in>>ok[i];
    for(i=1;i<=n;++i)
    {
        minim[i]=MAXINT;
        h[i]=i;
        poz[i]=i;
    }
    h[0]=n;
    minim[1]=0;
    for(i=1;i<=n;++i)
    {
        if (minim[h[1]]==MAXINT) break;
        x=h[1];
        scoate(x);
        //poz[x]=0;
        for(j=0;j<a[x].size();++j)
        {
            if(minim[x]+cost[a[x][j]]<minim[dr[a[x][j]]])
            {
                minim[dr[a[x][j]]]=minim[x]+cost[a[x][j]];
                urca(poz[dr[a[x][j]]]);
            }
        }
    }
    for(i=2;i<=n;++i)
    {
        if (minim[i]==MAXINT)
            out<<"0 ";
        else
            out<<minim[i]<<" ";
    }
    return 0;
}