#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],who[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;
                who[i]=i;
        }
        d[1]=0;
}



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


void heap_up(int i){
        int dad=i/2;
        if (dad){
                int min=i;
                if (d[dad]<d[min]){min=dad;}
                if (min==i){
                        int aux=d[dad];
                        d[dad]=d[i];
                        d[i]=aux;
                        aux=who[dad];
                        who[dad]=who[i];
                        who[i]=aux;
                        poz[who[i]]=i;
                        poz[who[min]]=min;
                        heap_up(dad);
                 }
        }
}


int extract_min(void){
        int aux=d[1];
        d[1]=d[dh];
        d[dh]=aux;
        aux=who[1];
        who[1]=who[dh];
        who[dh]=aux;
        poz[who[1]]=1;
        poz[who[dh]]=dh;
        dh--;
        heap_dw(1);
        return (who[dh+1]);
}


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


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