#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));
    }

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

    while (!Q.empty()) {
        const ncpair p = Q.top();
        Q.pop();

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

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

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