#include <fstream>
#include <queue>

#define NMAX 50010
#define MMAX 250010
#define MULT 60000000

using namespace std;

vector<int> graf[NMAX];
int N, M;
int ans[NMAX], flag[NMAX];

struct muchie {int x, y, c;} mG[MMAX];

void dijkstra (int A) {
    ans[A] = 0;

    priority_queue< pair <int, int>, vector <pair <int, int> >, greater <pair<int, int> > > PQ;

    for (int i = 1; i <= N; i++) {
        if (i != A) {
            ans[i] = MULT;
            flag[i] = 0;
        }
    }

    PQ.push (make_pair (ans[A], A));
    flag[A] = 1;

    while ( !PQ.empty ()) {
        int crt = PQ.top().second;
        PQ.pop();

        for (int i = 0; i < graf[crt].size (); i++) {
            int tmp = ans[crt] + mG[graf[crt][i]].c;

            if (tmp < ans[mG[graf[crt][i]].y]) {
                ans[mG[graf[crt][i]].y] = tmp;

                if ( !flag[mG[graf[crt][i]].y]) {
                    PQ.push (make_pair (tmp, mG[graf[crt][i]].y));
                    flag[mG[graf[crt][i]].y] = 1;
                }
            }
        }

    }
}

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

    scanf ("%d%d", &N, &M);
    for (int i = 1; i <= M; i++) {
        scanf ("%d%d%d", &mG[i].x, &mG[i].y, &mG[i].c);
        if (mG[i].c == 0) {
            continue;
        }
        graf[mG[i].x].push_back (i);
    }

    dijkstra (1);

    for (int i = 2; i <= N; i++) {
        if (ans[i] == MULT) {
            ans[i] = 0;
        }
        printf ("%d ", ans[i]);
    }
    printf ("\n");

    return 0;
}