# include <algorithm>
using namespace std;

# define DIM 1 << 16
# define INF 1 << 30

struct djk {
    int poz, val;
};

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

int n, m, cnt, h[DIM];
djk a[DIM];
graf *lst[DIM];

void add (int x, int y, int cost) {

    graf *p = new graf;

    p->nod = y;
    p->cost = cost;
    p->urm = lst[x];
    lst[x] = p;
}

void init () {

    int i;

    for (i = 2; i <= n; ++ i) {

        a[i].val = INF;
        a[i].poz = -1;
    }
}

void swap (int x, int y) {

    int aux;

    aux = h[x];
    h[x] = h[y];
    h[y] = aux;
}

void uph (int k) {

    int aux;

    while (k > 1) {

        aux = k >> 1;
        if (a[h[aux]].val > a[h[k]].val) {

            a[h[k]].poz = aux;
            a[h[aux]].poz = k;
            swap (aux, k);
            k = aux;
        }

        else
            return;
    }
}

void downh (int k) {

    int aux;

    while ( k <= cnt) {

        aux = k;
        if ((k << 1) <= cnt) {

            aux = k << 1;
            if (aux + 1 <= cnt)
                if (a[h[aux + 1]].val < a[h[aux]].val)
                    ++ aux;
        }

        else
            return;

        if (a[h[k]].val > a[h[aux]].val) {

            a[h[k]].poz = aux;
            a[h[aux]].poz = k;
            swap (k, aux);
            k = aux;
        }

        else
            return;
    }
}

void insert (int k) {

    h[++ cnt] = k;
    a[h[cnt]].poz = cnt;
    uph (cnt);
}

void cut () {

	h[1] = h[cnt --];
	a[h[1]].poz = 1;
	downh (1);
}

void dijkstra () {

	int aux;
	graf *p;

    a[1].poz = 1;
    h[++ cnt] = 1;
	while (cnt) {

		aux = h[1];
		cut ();
        for (p = lst[aux]; p; p = p->urm)
            if (a[aux].val + p->cost < a[p->nod].val) {

                a[p->nod].val = a[aux].val + p->cost;
                if (a[p->nod].poz != -1)
					uph (a[p->nod].poz);

                else
                    insert (p->nod);
            }
    }
}

void solve () {

    int i, x, y, cost;

    scanf ("%d%d", &n, &m);
    for (i = 0; i < m; ++ i) {

        scanf ("%d%d%d", &x, &y, &cost);
        add(x,y,cost);
    }
    init ();
    dijkstra ();
    for (i = 2; i <= n; ++ i)

        if (a[i].val == INF)
            printf ("0 ");

        else
            printf ("%d ", a[i].val);
}

int main () {

    freopen ("dijkstra.in", "r", stdin);
    freopen ("dijkstra.out", "w", stdout);

    solve ();

    return 0;
}