#include<stdio.h>
#include<stdlib.h>

#define N 50005
#define INF 2000000000

int sol[N], n, m;
bool fol[N];

typedef struct cc{int v,co;} rec;
rec *a[N];

void citire(), BF(), afisare();

int main (){
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    citire(); BF(); afisare();

    return 0;
}

void citire(){
int i, x, y, z;

    scanf("%d %d",&n, &m);

    for (i = 1; i <= n; i++)
        a[i] = (rec*) malloc (sizeof (rec) ),a[i][0].v=0;

    for ( ; m; m--){
        scanf("%d %d %d", &x, &y, &z);
        a[x][0].v++; a[x] = (rec*) realloc (a[x], (a[x][0].v+1)* sizeof(rec));
        a[x][a[x][0].v].v = y; a[x][a[x][0].v].co = z;
    }
}

void BF(){
int i, j, q[2*N], x, p, u;
    q[0] = 1; sol[1] = 0; fol[1] = 1;
    for (i = 2; i <= n; i++) sol[i] = INF;

    for (p = 0, u = 0; p <= u; p++){
        x = q[p];
        for (i = 1; i <= a[x][0].v; i++)
            if (sol[x] + a[x][i].co < sol[a[x][i].v] ){
                sol[a[x][i].v] = sol[x] + a[x][i].co;
                if (!fol[a[x][i].v]) q[++u] = a[x][i].v, fol[a[x][i].v] = 1;
            }
        fol[x] = 0;
    }
}

void afisare(){
    for (int i = 2; i <= n; i++)
        printf("%d ", (sol[i] < INF ? sol[i] : 0));
    printf("\n");
}