#include <cstdio>
#include <vector>
#include <queue>
#include <utility>

#define FILEIN "dijkstra.in"
#define FILEOUT "dijkstra.out"

using namespace std;

const int NMAX = 50005;
const int INF  = 0x3f3f3f3f;
vector<int> C[NMAX]; // cost
vector<int> A[NMAX]; // adiacenta
queue<pair<int, int> > Q;
int N, M;
int D[NMAX];

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d %d", &N, &M);
    for ( int i = 1; i <= N; i++ ) {
        D[i] = INF;
    }

    for ( int i = 1, x, y, d; i <= M; i++ ) {
        scanf("%d %d %d", &x, &y, &d);
        A[x].push_back(y);
        C[x].push_back(d);
    }

    /* Dijkstra */

    D[1] = 0;
    Q.push(make_pair(1,0));
    while (!Q.empty()) {
        int d, x;
        x = Q.front().first;
        d = Q.front().second;
        Q.pop();
        for ( int i = 0; i < A[x].size(); i++) {
            if ( d + C[x][i] < D[A[x][i]]) {
                D[A[x][i]] = d + C[x][i];
                Q.push(make_pair(A[x][i], D[A[x][i]]));
            }
        }
    }

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

    return 0;
}