#include <iostream>
#define INFINITE 2000000000
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define MAX_N 50000
struct list{
        int inf,c;
        list *urm;
} *rel[MAX_N+1];
int d[MAX_N+1],dh;
int poz[MAX_N+1],h[MAX_N+1],n,m;

void iofile(void){
        freopen(FIN,"rt",stdin);
        freopen(FOUT,"wt",stdout);
        scanf("%d%d",&n,&m);
        dh=n;
        list* q;
        for (int i=1,x,y,cst;i<=m;i++){
                scanf("%d%d%d",&x,&y,&cst);
                q=new list;
                q->inf=y;
                q->c=cst;
                q->urm=rel[x];
                rel[x]=q;
        }
        fclose(stdin);
        for (int i=1;i<=n;i++){
                d[i]=INFINITE;
                poz[i]=i;
                h[i]=i;
        }
        d[1]=0;
}


void swap(int i,int j){
        int aux=h[i];h[i]=h[j];h[j]=aux;
        poz[h[i]]=i;
        poz[h[j]]=j;
}


void heap_dw(int i){
        int l=2*i,r=2*i+1,min=i;
        if (l<=dh && d[h[l]]<d[h[min]]){min=l;};
        if (r<=dh && d[h[r]]<d[h[min]]){min=r;};
        if (min!=i){
                swap(i,min);
                heap_dw(min);
        }
}


void heap_up(int i){
        int dad=i/2;
        if (dad){
                if (d[h[i]]<d[h[dad]]){swap(i,dad);heap_up(dad);}
        }
}


int extract_min(void){
        swap(1,dh);
        dh--;
        heap_dw(1);
        return (h[dh+1]);
}


void dijkstra(void){
        dh=n;
        while (dh){
                int nmin=extract_min();
                for (list *p=rel[nmin];p;p=p->urm){
                        if (d[p->inf]>d[nmin]+p->c){
                                d[p->inf]=d[nmin]+p->c;
                                heap_up(poz[p->inf]);
                                }
                }
        }
        for (int i=2;i<=n;i++){
                if (d[i]==INFINITE){printf("%d ",0);} else{
                        printf("%d ",d[i]);}}
        printf("\n");
        fclose(stdout);
}


int main(void){
        iofile();
        dijkstra();
        return 0;
}