#include <stdio.h>
FILE *f=fopen("dijkstra.in","r"),*g=fopen("dijkstra.out","w");
int n,m,d[50001],i,x,y,c,viz[50001],min;
struct nod{int y; int c; nod* next;};
nod *L[50001],*u[50001];
int main(void)
{
    fscanf(f,"%d%d",&n,&m);
    for (i=0;i<=n;i++)
    {
        d[i]=2000000000;
        L[i]=new nod;
        L[i]->y=0;
        L[i]->c=0;
        L[i]->next=NULL;
        u[i]=new nod;
        u[i]=L[i];
    }
    nod *nou;
    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&c);
        nou=new nod;
        nou->y=y;
        nou->c=c;
        nou->next=NULL;
        u[x]->next=nou;
        u[x]=u[x]->next;
    }
    d[1]=0;
    while (viz[0]<n)
    {
        min=0;

        for (i=1;i<=n;i++)
        {
            if (d[i]<d[min] && !viz[i])
                min=i;
        }
        viz[min]=1;
        viz[0]++;
        while (L[min]!=u[min])
        {
            L[min]=L[min]->next;
            if (d[L[min]->y]>d[min]+L[min]->c)
                d[L[min]->y]=d[min]+L[min]->c;
        }
    }
    for (i=2;i<=n;i++)
    {
        if (d[i]==2000000000) fprintf(g,"0 ");
        else fprintf(g,"%d ",d[i]);
    }
    fprintf(g,"\n");
    fclose(g);
    return 0;
}