#include <iostream>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

struct way {
    int x, y, c;

    bool operator < (const way& d1) const {
        return c < d1.c;
    }
};

struct nodeC {
    int node, C;

    bool operator < (const nodeC& d1) const {
        return C > d1.C;
    }
};

int N, M;
vector<vector<way>> G;
vector<int> D;
vector<bool> V;

void dijkstra(int node) {
    D[node] = 0;
    priority_queue<nodeC> Q;
    nodeC n;
    n.node = node;
    n.C = 0;
    Q.push(n);

    while(!Q.empty()) {
        n = Q.top();
        Q.pop();
        if(V[n.node])
            continue;
        V[n.node] = true;

        for(way neigh : G[n.node]) {
            if(D[neigh.y] > neigh.c + D[n.node]) {
                D[neigh.y] = neigh.c + D[n.node];
                nodeC next;
                next.node = neigh.y;
                next.C = D[neigh.y];
                Q.push(next);
            }
        }
    }
}

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

    cin >> N >> M;

    G.resize(N + 1);
    D.resize(N + 1);
    V.resize(N + 1);
    fill(D.begin(), D.end(), INT_MAX);
    fill(V.begin(), V.end(), false);

    for(int i = 1; i <= M; i++) {
        int x, y, c;
        cin >> x >> y >> c;

        way drum;
        drum.x = x;
        drum.y = y;
        drum.c = c;

        G[x].push_back(drum);
    }

    dijkstra(1);

    for (int i = 2; i <= N; i++) {
        if(INT_MAX == D[i]) {
            D[i] = 0;
        }
        printf("%d ", D[i]);
    }

    return 0;
}