#include <iostream>
#include <fstream>
#include <queue>
#include <vector>


template <class _elem, typename compare_by>
class heap {
public:
    heap(size_t _size = 1024) : max_size(_size),
        current_bound(1) {
        storage = new _elem[max_size];
    }

    heap(const heap<_elem, compare_by>& target) { *this = target; }

    heap& operator = (const heap<_elem, compare_by>& target) {
        delete[] storage;
        max_size = target.max_size;
        storage = new _elem[max_size];
        for (unsigned i = 0; i < max_size; ++i)
            storage[i] = target.storage[i];
        current_bound = target.current_bound;
    }

    [[gnu::pure]] inline bool empty() { return (current_bound == 1); }

    [[gnu::pure]] inline _elem top() { return storage[1]; }

    [[gnu::pure]] inline _elem last_item() { return storage[0]; }

    [[gnu::hot]] inline void add(_elem target) {
        storage[current_bound] = target;
        sift_up(current_bound);
#ifdef DYNAMIC_ALLOC
        if (++current_bound == max_size) {
            max_size <<= 1;
            realloc(storage, max_size);
        }
#else
        ++current_bound;
#endif
    }

    [[gnu::hot]] inline _elem pop() {
        storage[0] = storage[1];
        storage[1] = storage[--current_bound];

        sift_down(1);

        return storage[0];
    }

    ~heap() { delete[] storage; }

private:
    [[gnu::hot]] inline void sift_up(unsigned crawler) {
        _elem aux = storage[crawler];

        while (parent_pos(crawler) && comparator(aux, parent(crawler))) {
            storage[crawler] = parent(crawler);
            crawler = parent_pos(crawler);
        }

        storage[crawler] = aux;
    }

    [[gnu::hot]] inline void sift_down(unsigned crawler) {
        _elem aux = storage[crawler];

        while (!is_leaf(crawler)) {
            if (!comparator(aux, left_son(crawler)) &&
                !comparator(right_son(crawler), left_son(crawler))) {
                storage[crawler] = left_son(crawler);
                crawler = left_son_pos(crawler);
            }
            else if (!comparator(aux, right_son(crawler))) {
                storage[crawler] = right_son(crawler);
                crawler = right_son_pos(crawler);
            }
            else {
                break;
            }
        }

        storage[crawler] = aux;
    }

    [[gnu::hot, gnu::pure]] inline unsigned right_son_pos(unsigned pos) {
        return 1 + (pos << 1);
    }

    [[gnu::hot, gnu::pure]] inline _elem right_son(unsigned pos) {
        return storage[right_son_pos(pos)];
    }

    [[gnu::hot, gnu::pure]] inline unsigned left_son_pos(unsigned pos) {
        return (pos << 1);
    }

    [[gnu::hot, gnu::pure]] inline _elem left_son(unsigned pos) {
        return storage[left_son_pos(pos)];
    }

    [[gnu::hot, gnu::pure]] inline unsigned parent_pos(unsigned pos) {
        return (pos >> 1);
    }

    [[gnu::hot, gnu::pure]] inline _elem parent(unsigned pos) {
        return storage[parent_pos(pos)];
    }

    [[gnu::hot]] inline bool is_leaf(unsigned pos) {
        return !(right_son_pos(pos) < current_bound && left_son_pos(pos) < current_bound);
    }

    compare_by comparator;
    size_t max_size, current_bound;
    _elem* storage;
};

constexpr int INF = (1LL << 31) - 1;

struct edge {
    int to, cost;
};

struct edge_comparator {
    inline bool operator ()(const edge& a, const edge& b) {
        return a.cost < b.cost;
    }
};

struct ext_edge : public edge {
    int from;
};

std::vector <edge> graph[50010];
int distance[50010], number_of_nodes;
/*
void dijkstra(int nod) {
    for (int i = 1; i <= n; ++i) d[i] = oo;
    d[nod] = 0;
    heap.push({ nod,0 });
    while (!heap.empty()) {
        int nod = heap.top().nod, c = heap.top().c;
        heap.pop();
        if (d[nod] != c) continue;
        for (vector <edge>::iterator i = v[nod].begin(); i < v[nod].end(); advance(i, 1))
            if (d[i->nod] > d[nod] + i->c)
                d[i->nod] = d[nod] + i->c, heap.push({ i->nod,d[i->nod] });
    }
}
*/
void dijkstra(unsigned start) {
    heap<ext_edge, edge_comparator> h;
    unsigned relaxed_nodes = 0;

    auto add_edges = [&h](unsigned node) mutable {
        for (auto iterator : graph[node]) {
            h.add(ext_edge{ iterator.to, iterator.cost, (int)node });
        }
    };

    for (auto& iterator : distance) {
        iterator = INF;
    }

    add_edges(start);
    distance[start] = 0;

    while (++relaxed_nodes < number_of_nodes) {
        while (distance[h.top().to] != INF)
            h.pop();

        auto current = h.top();
        distance[current.to] = distance[current.from] + current.cost;
        add_edges(current.to);
    }
};
int main() {
    std::ifstream f("dijkstra.in");
    std::ofstream t("dijkstra.out");
    int x, y, c, m;
    f >> number_of_nodes >> m;
    for (int i = 0; i < m; ++i)
        f >> x >> y >> c,
        graph[x].push_back({ y,c });
    dijkstra(1);
    for (int i = 2; i <= number_of_nodes; ++i)
        if (distance[i] == INF) t << "0 ";
        else t << distance[i] << " ";
    return 0;
}