#include <fstream>
#include <bitset>
#include <vector>
#include <queue>
const std :: string programName = "dijkstra";
std :: ifstream f(programName + ".in");
std :: ofstream g(programName + ".out");
const int MAX = 5E4, INF = 0x7E7E7E7E;
int N, M, Dist[MAX + 5];
std :: bitset <MAX + 5> use;
std :: vector < std :: pair <int, int> > Graph[MAX + 5];
struct HeapNode {
    int node, cost;
    HeapNode(int n, int c) : node(n), cost(c) {}
    bool operator < (const HeapNode &other) const {
        return cost > other.cost;
    }
};
std :: priority_queue <HeapNode> queue;
void read();
void print();
void Dijkstra();
int main() {
    read();
    Dijkstra();
    print();
    return 0x0;
}
void read() {
    f >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y, cost;
        f >> x >> y >> cost;
        Graph[x].emplace_back(y, cost);
    }
}
void print() {
    for (int i = 2; i <= N; ++i)
        g << (Dist[i] == INF ? 0 : Dist[i]) << ' ';
    g << "\n";
}
void Dijkstra() {
    for (int i = 2; i <= N; ++i)
        Dist[i] = INF;
    queue.emplace(1, 0);
    while (!queue.empty()) {
        int Node = queue.top().node;
        int cost = queue.top().cost;
        queue.pop();
        if (cost != Dist[Node])
            continue;
        for (const auto &it : Graph[Node]) {
            if (Dist[it.first] > cost + it.second) {
                Dist[it.first] = cost + it.second;
                queue.emplace(it.first, cost + it.second);
            }
        }
    }
}