#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
#include <unordered_map>
#include <memory>
#include <deque>
#include <queue>

using namespace std;

struct ncpair {
    int node;
    int cost;
    ncpair(int node_, int cost_): node(node_), cost(cost_) {}
};

int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    int N, M;
    f >> N >> M;

    vector<ncpair> G[N];

    for (int i = 0; i < M; i++) {
        int a, b, c;
        f >> a >> b >> c;
        --a; --b;
        G[a].push_back(ncpair(b, c));
    }

    const int INF = 1e9 + 100;
    vector<int> cost(N, INF);
    cost[0] = 0;
    struct cmp {
        bool operator() (const ncpair& l, const ncpair& r) const { return l.cost < r.cost || (l.cost == r.cost && l.node < r.node); }
    };
    set<ncpair, cmp> Q;
    Q.insert(ncpair(0, 0));

    while (!Q.empty()) {
        const ncpair p = *Q.begin();
        Q.erase(Q.begin());
        if (p.cost != cost[p.node])
            continue;

        for (const ncpair& edge : G[p.node])
            if (cost[edge.node] > cost[p.node] + edge.cost) {
                if (cost[edge.node] < INF) {
                    //Q.erase(ncpair(edge.node, cost[edge.node]));
                }
                cost[edge.node] = cost[p.node] + edge.cost;
                Q.insert(ncpair(edge.node, cost[edge.node]));
            }
    }

    for (int i = 1; i < N; i++)
        g << (cost[i] < INF ? cost[i] : 0) << ' ';
    g << '\n';

    f.close();
    g.close();
    return 0;
}