#include <cstdio>
#define INF 0x3f3f3f3f
using namespace std;

FILE *f;
FILE *g;

typedef struct nod
{
    int inf,c;
    nod *urm;
} NOD;
typedef NOD *graf[50010];
graf G;

NOD *C,*Cu,*p,*q;

int n,m,d[50010];

void citire()
{
    f=fopen("dijkstra.in","r");
    fscanf(f,"%d %d",&n,&m);
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&a,&b,&c);
        p=new NOD;
        p->inf=b; p->urm=G[a]; p->c=c;
        G[a]=p;
    }
    fclose(f);
}

void init()
{
    for(int i=1;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    C=new NOD;
    C->inf=1;
    C->urm=NULL;
    Cu=C;
}

void bell()
{
    init();
    while(C)
    {
        p=G[C->inf];
        while(p)
        {
            if(d[p->inf]>d[C->inf]+p->c)
            {
                d[p->inf]=d[C->inf]+p->c;
                q=new NOD;
                Cu->urm=q;
                q->inf=p->inf;
                q->urm=NULL;
                Cu=q;
            }
            p=p->urm;
        }
        C=C->urm;
    }
}

int main()
{
    citire();
    bell();
    g=fopen("dijkstra.out","w");
    for(int i=2;i<=n;i++)
        fprintf(g,"%d ",d[i]<INF?d[i]:0);
    fprintf(g,"\n");
    fclose(g);
    return 0;
}