#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#define node first
#define cost second

using namespace std;

const int NMAX = 50003, INF = 2e9;

int C[NMAX];

struct predicate {

    bool operator () (const int a, const int b) {

        return C[a] > C[b];

    }

};

priority_queue <int, vector<int>, predicate> Q;
vector< pair<int, int> > graph[NMAX];

int main () {

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

    int N, M;
    scanf ("%d%d", &N, &M);

    while (M--) {
        int a, b, c;
        scanf ("%d%d%d", &a, &b, &c);
        graph[a].push_back(make_pair (b, c));
    }

    for (int i = 2; i <= N; ++i)
        C[i] = INF;

    Q.push (1);
    while (!Q.empty()) {
        int node;

        node = Q.top();
        Q.pop();
        for (auto i : graph[node])
            if (C[i.node] > C[node] + i.cost) {
                C[i.node] = C[node] + i.cost;
                Q.push (i.node);
            }

    }

    for (int i = 2; i <= N; ++i)
        if (C[i] == INF)
        printf ("0 ");
    else
        printf ("%d ", C[i]);

}