#include <cstdio>
using namespace std;

int h=1,poz[50001],heap[50002],d[50001];

struct graf
{
    int v,c;
    graf *u;
}*nod[50001];

/*void parcurgere_adancime(graf *x,int y)
{
    while(x!=NULL)
    {
        printf("%d %d %d\n",y+1,x->v+1,x->c);
        parcurgere_adancime(nod[x->v],x->v);
        x=x->u;
    }
}*/

void urca(int i)
{
    int aux=heap[i];
    while(i>1&&aux<d[heap[i>>1]])
    {
        heap[i]=heap[i>>1];
        poz[heap[i]]=i;
        i>>=1;
    }
    heap[i]=aux;
    poz[aux]=i;
}

void coboara(int i)
{
    int j,aux;
    do
    {
        j=0;
        if(i<<1<=h)
        {
            j=i<<1;
            if(d[heap[j]]>d[heap[j+1]]&&j+1<=h) ++j;
            if(d[heap[j]]>=d[heap[i]]) j=0;
        }
        if(j)
        {
            poz[heap[j]]=i;
            poz[heap[i]]=j;
            aux=heap[j];
            heap[j]=heap[i];
            heap[i]=aux;
            i=j;
        }
    }
    while(j);
}

void adauga(int i)
{
    heap[++h]=i;
    poz[i]=h;
    urca(h);
}

void sterge(int i)
{
    poz[heap[i]]=-1;
    heap[i]=heap[h--];
    coboara(i);
}

void showheap()
{
    int y=2;
    for(int i=1;i<=h;++i)
    {
        printf("%d ",heap[i]);
        if(i==y-1)
        {
            printf("\n");y*=2;
        }
    }
    printf("\n\n");
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m,i,j;
    graf *nod1;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;++i)
    {
        scanf("%d",&j);
        nod1=new graf;
        nod1->u=nod[j];
        nod[j]=nod1;
        scanf("%d",&j);
        nod1->v=j;
        scanf("%d",&j);
        nod1->c=j;
    }
  //  parcurgere_adancime(nod[0],0);
    for(i=2;i<=n;++i)
    {
        d[i]=-1;
    }
    heap[1]=1;
    while(h)
    {
        nod1=nod[heap[1]];
        while(nod1)
        {
            if(!poz[nod1->v])
            {
                d[nod1->v]=d[heap[1]]+nod1->c;
                adauga(nod1->v);
            }
            else
            {
                if(poz[nod1->v]!=-1)
                {
                    j=d[heap[1]]+nod1->c;
                    if(d[nod1->v]>j)
                    {
                        d[nod1->v]=j;
                        urca(poz[nod1->v]);
                    }
                }
            }
            nod1=nod1->u;
        }
        // showheap();
        sterge(1);
    }
    for(i=2;i<=n;++i)
    {
        if(d[i]==-1) printf("0 ");
        else printf("%d ",d[i]);
    }
    printf("\n");
    return 0;
}