#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; }
    } cmps;
    priority_queue<ncpair, vector<ncpair>, cmp> Q(cmps);
    Q.push(ncpair(0, 0));
 
    while (!Q.empty()) {
        const ncpair p = Q.top();
        Q.pop();
        if (p.cost != cost[p.node])
            continue;
 
        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] < INF ? cost[i] : 0) << ' ';
    g << '\n';
 
    f.close();
    g.close();
    return 0;
}