#include <stdio.h>
#define NIL -1
#define MAXN 50000
#define MAXM 250000
int heap[MAXN+1], poz[MAXN+1], luat[MAXN+1], d[MAXN+1], cost[MAXM+1], val[MAXM+1], next[MAXM+1], lista[MAXN+1], n, k;
inline int tata(int a){
    return (a-1)/2;
}
inline int fiust(int a){
    return (a*2)+1;
}
inline int fiudr(int a){
    return (a*2)+2;
}
inline void adaug(int x, int y, int c){
    k++;
    cost[k]=c;
    val[k]=y;
    next[k]=lista[x];
    lista[x]=k;
}
inline void schimb(int a, int b){
    int aux;
    aux=heap[a];
    heap[a]=heap[b];
    heap[b]=aux;
    poz[heap[a]]=a;
    poz[heap[b]]=b;
}
inline void coborare(int p){
    int q, f;
    f=1;
    while(f==1){
        q=NIL;
        if(fiudr(p)<n){
            q=fiudr(p);
        }
        if((fiust(p)<n)&&((q==NIL)||(d[heap[q]]>d[heap[fiust(p)]]))){
            q=fiust(p);
        }
        if((q!=NIL)&&(d[heap[q]]<d[heap[p]])){
            schimb(q, p);
            p=q;
        }else{
            f=NIL;
        }
    }
}
inline void urcare(int p){
    while((p!=0)&&(d[heap[p]]<d[heap[tata(p)]])){
        schimb(p, tata(p));
        p=tata(p);
    }
}
int main(){
    int m, x, y, z, p, i, cn;
    FILE *fin, *fout;
    fin=fopen("dijkstra.in", "r");
    fout=fopen("dijkstra.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    cn=n;
    k=0;
    for(i=0; i<m; i++){
        fscanf(fin, "%d%d%d", &x, &y, &z);
        adaug(x, y, z);
    }
    n=1;
    heap[0]=1;
    d[1]=0;
    poz[1]=0;
    while(n>0){
        p=lista[heap[0]];
        while(p!=0){
            if(luat[val[p]]==0){
                luat[val[p]]=1;
                d[val[p]]=d[heap[0]]+cost[p];
                heap[n]=val[p];
                poz[val[p]]=n;
                n++;
                urcare(n-1);
            }else if(d[val[p]]>d[heap[0]]+cost[p]){
                d[val[p]]=d[heap[0]]+cost[p];
                urcare(poz[val[p]]);
            }
            p=next[p];
        }
        n--;
        heap[0]=heap[n];
        poz[heap[0]]=0;
        coborare(0);
    }
    for(i=2; i<cn; i++){
        fprintf(fout, "%d ", d[i]);
    }
    fprintf(fout, "%d\n", d[cn]);
    fclose(fin);
    fclose(fout);
    return 0;
}