#include <cstdio>
#include <cstring>
#define NMAX 50000
#define INF 1<<30;

using namespace std;

struct nod {
    int inf, cost;
    nod * urm;
};

nod *a[NMAX];
bool viz[NMAX];
int n, m, d[NMAX];

void add (int x, int y, int z) {
    nod *p;
    p = new nod;
    p->cost = z;
    p->inf = y;
    p->urm = a[x];
    a[x] = p;
}

void read () {
    scanf ("%d%d", &n, &m);
    int i, x, y, z;
    for (i=1; i<=m; ++i) {
        scanf ("%d%d%d", &x, &y, &z);
        add (x, y, z);
    }
}

void dijkstra () {
    //memset (d, INF, sizeof(d));
    int i, min, j, v;
    for (i=2; i<=n; ++i)
        d[i] = INF;
    nod *p;
    p = a[1];
    while (p) {
        d[p->inf] = p->cost;
        p = p->urm;
    }
    for (i=1; i<=n; ++i)
        viz[i] = false;
    for (i=1; i<=n; ++i) {
        min = INF;
        for (j=2; j<=n; ++j)
            if (viz[j]==false && min>d[j]) {
                min = d[j];
                v = j;
            }
        //printf ("%d ", v);
        p = a[v];
        viz[v] = true;
        while (p) {
            if (d[v]+p->cost < d[p->inf] && viz[p->inf]==false)
                d[p->inf] = d[v] + p->cost;
            p = p->urm;
        }
    }
}

void write () {
    for (int i=2; i<=n; ++i) {
        if (d[i] != 1<<30)
            printf ("%d ", d[i]);
        else printf ("0 ");
    }
}

int main () {
    freopen ("dijkstra.in", "r", stdin);
    read ();
    fclose (stdin);
    dijkstra ();
    freopen ("dijkstra.out", "w", stdout);
    write ();
    fclose (stdout);
    return 0;
}