#include<stdio.h>
#include<stdlib.h>
#define INF 2000000000
typedef struct nod{ int x,d; nod *urm;}NODE;
NODE *v[50001];
int n,m,D[50001],P[50001];
short V[50001];

void citire()
{
    FILE*f=fopen("dijkstra.in","r");
    NODE *p;
    fscanf(f,"%d%d",&n,&m);
    int x,y,d;
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d%d%d",&x,&y,&d);
        p=(NODE*)malloc(sizeof(NODE));
        p->x=y;
        p->d=d;
        p->urm=v[x];
        v[x]=p;
        p=(NODE*)malloc(sizeof(NODE));
        p->x=x;
        p->d=d;
        p->urm=v[y];
        v[y]=p;
    }
}

void dijkstra()
{
    for(int i=0;i<=n;++i) D[i]=INF;
    D[1]=0;
    int min;
    do
    {
        min=0;
        for(int i=1;i<=n;++i)
            if(!V[i]&&D[i]<D[min])  min=i;

            NODE *q=v[min];
            V[min]=1;

            while(q&&min)
            {
                if(D[min]+q->d < D[q->x])
                {
                    D[q->x]=D[min] + q->d;
                    P[q->x] = min;
                }
                q=q->urm;
            }
    }while(min);

}

void scriere()
{
    FILE *f=fopen("dijkstra.out","w");
    for(int i=2;i<=n;++i)
        if(D[i]!=INF) fprintf(f,"%d ",D[i]);
        else fprintf(f,"0 ");
    fclose(f);
}

int main()
{
    citire();
    dijkstra();
    scriere();
    return 0;
}