#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int DMAX = 50003, MAX = 2e9;
int best[DMAX];

int main () {

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

    vector <int> G[DMAX], C[DMAX];
    queue <int> q;
    int N, M, a, b, c, i;

    scanf ("%d%d", &N, &M);
    for (i = 2; i <= N; ++i)
        best[i] = MAX;
    for (i = 1; i <= M; ++i)
        scanf ("%d%d%d", &a, &b, &c), G[a].push_back (b), C[a].push_back (c);
    q.push (1);
    while (!q.empty ()) {
        a = q.front ();
        q.pop ();
        for (i = 0; i < G[a].size (); ++i)
            if (best[G[a][i]] > best[a] + C[a][i])
                best[G[a][i]] = best[a] + C[a][i], q.push (G[a][i]);
    }
    for (i = 2; i <= N; ++i)
        if (best[i] != MAX)
            printf ("%d ", best[i]);
        else
            printf ("0 ");

}