#include<fstream.h>
#define Nmax 5005
#define inf 60000000

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

struct muchie{int vec,cost;muchie* next;};
typedef muchie* lista;
lista a[Nmax];

int N,M;
int d[Nmax],viz[Nmax];

int main(){

    fscanf(fin,"%d %d",&N,&M);

    for(int i=1;i<=M;i++){
            int x,y,d;
            fscanf(fin,"%d%d%d",&x,&y,&d);
            lista aux=new muchie;
            aux->vec=y;
            aux->cost=d;
            aux->next=a[x];
            a[x]=aux;
    }

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

    d[1]=0;
    for(int i=1;i<=N;i++){

            int min=inf,poz;
            for(int j=1;j<=N;j++)
                if(viz[j]==0 && min>d[j])
                    min=d[j],poz=j;

            viz[poz]=1;
            for(lista p=a[poz];p;p=p->next)
                if(d[p->vec]>d[poz]+p->cost)
                    d[p->vec]=d[poz]+p->cost;

    }

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

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

}