#include<stdio.h>
#define Nmax 50005
#define Mmax 250005
#define inf 2000000000

FILE *fin=fopen("dijkstra.in","r"),
    *fout=fopen("dijkstra.out","w");

int N,M,dist[Nmax];
char viz[Nmax];

struct nod{int vec,d;nod* next;};
typedef nod* lista;
lista L[Nmax];

struct elem{int poz;elem* next;};
typedef elem* coada;
coada Q,Qf;

int main(){
    fscanf(fin,"%d %d",&N,&M);
    for(int i=1;i<=M;i++){
        int x,y,l;
        fscanf(fin,"%d %d %d",&x,&y,&l);

        lista aux=new nod;
        aux->vec=y;
        aux->d=l;
        aux->next=L[x];
        L[x]=aux;
    }

    for(int i=1;i<=N;i++)
        dist[i]=inf;

    Q=Qf=new elem;
    Q->poz=1;
    Q->next=NULL;
    dist[1]=0;
    viz[1]=1;

    while(Q){

        int crt=Q->poz;

        for(lista p=L[crt];p;p=p->next)
            if(dist[p->vec] > dist[crt]+p->d){
                dist[p->vec]=dist[crt]+p->d;
                if(viz[p->vec]==0){
                    viz[p->vec]=1;
                    Qf->next=new elem;
                    Qf=Qf->next;
                    Qf->poz=p->vec;
                    Qf->next=NULL;
                }
            }

        viz[crt]=0;
        coada aux=Q;
        Q=Q->next;
        delete aux;
    }

    for(int i=2;i<=N;i++)
        if(dist[i]!=inf)
            fprintf(fout,"%d ",dist[i]);
        else
            fprintf(fout,"0 ");


    fclose(fin);
    fclose(fout);
    return 0;
}