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

#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <fcntl.h>
#include <unistd.h>

class parser {
public:
    inline parser() {
        /// default c-tor
    }

    inline parser(const char* file_name) {
        int fd = open(file_name, O_RDONLY);
        index &= 0;
        fstat(fd, &sb);
        buffer = (char*)mmap(0, sb.st_size, PROT_READ, MAP_PRIVATE | MAP_NORESERVE, fd, 0);
        close(fd);
    }

    template <typename T>
    inline parser& operator >> (T& n) {
        n &= 0;
        for (; buffer[index] < '0' or buffer[index] > '9'; ++index);
#ifdef SIGNED
        sign &= 0;
        sign = (buffer[(index ? index - 1 : 0)] == '-');
#endif
        for (; '0' <= buffer[index] and buffer[index] <= '9'; ++index)
            n = (n << 3) + (n << 1) + buffer[index] - '0';
#ifdef SIGNED
        n ^= ((n ^ -n) & -sign);
#endif
        return *this;
    }

    ~parser() {
        munmap(buffer, sb.st_size);
    }

private:
    struct stat sb;
    int index;
#ifdef SIGNED
    int sign;
#endif
    char* buffer;
};

class writer {
public:
    writer() {};

    writer(const char* file_name) {
        output_file.open(file_name, std::ios::out | std::ios::binary);
        output_file.sync_with_stdio(false);
        index &= 0;
    }

    template <typename T>
    inline writer& operator <<(T target) {
        auto inc = [&, this]() mutable {
            if (++index == SIZE)
                index &= 0,
                output_file.write(buffer, SIZE);
        };

        aux &= 0;
#ifdef SIGNED_WRITE
        sign = 1;
        if (target < 0)
            sign = -1;
#endif  // SIGNED_WRITE
        if (target == 0) {
            buffer[index] = '0';
            inc();
            return *this;
        }
        for (; target; target = target / 10)
#ifndef SIGNED_WRITE
            nr[aux++] = target % 10 + '0';
#else
            nr[aux++] = (sign * target) % 10 + '0';
        if (sign == -1)
            buffer[index] = '-', inc();
#endif  // SIGNED_WRITE
        for (; aux; inc())
            buffer[index] = nr[--aux];
        return *this;
    }

    inline writer& operator <<(const char* target) {
        auto inc = [&, this]() mutable {
            if (++index == SIZE)
                index &= 0,
                output_file.write(buffer, SIZE);
        };

        aux &= 0;
        while (target[aux])
            buffer[index] = target[aux++], inc();
        return *this;
    }

    inline void close() {
        delete this;
    }

    ~writer() {
        output_file.write(buffer, index);
        output_file.close();
    }

private:
    static const int SIZE = 0x200000; ///2MB
    int index, aux;
#ifdef SIGNED_WRITE
    int sign;
#endif  // SIGNED_WRITE
    char buffer[SIZE], nr[24];
    std::fstream output_file;
};

#define LIKELY(condition) __builtin_expect(static_cast<bool>(condition), 1)
#define UNLIKELY(condition) __builtin_expect(static_cast<bool>(condition), 0)

template <class Tkey, class Tinfo, class _hasher = std::hash<Tkey>>
class hashtable {
public:
    struct data_cell {
        Tkey first;
        Tinfo second;
    };

    hashtable() {
        container = new data_cell[SIZE];
    }; //C-TOR

    inline data_cell* add(Tkey target, Tinfo info) {
        set_index_to(target);

        while (true) {
            if (container[get_pointer_pos()].first == target) {
                occupied[get_pointer_pos()] = 2;
                return pointer;
            }
            else if (occupied[get_pointer_pos()] < 2) {
                container[get_pointer_pos()].first = target;
                container[get_pointer_pos()].second = info;
            }
            else {
                inc();
            }
        }
    }

    void erase(Tkey target) {
        set_index_to(target);

        while (true) {
            if (container[get_pointer_pos()].first == target) {
                occupied[get_pointer_pos()] = 1;
                return;
            }
            else if (!occupied[get_pointer_pos()]) {
                return;
            }
            else {
                inc();
            }
        }
    }

    inline Tinfo& operator [] (Tkey target) {
        if (find(target) != end()) {
            return find(target)->second;
        } else {
            return add(target, Tinfo())->second;
        }
    }

    [[gnu::hot]] inline data_cell*& find(Tkey target) {
        set_index_to(target);

        while (true) {
            if (LIKELY(container[get_pointer_pos()].first == target && occupied[get_pointer_pos()] == 2)) {
                return pointer;
            }
            else if ((container[get_pointer_pos()].first == target && occupied[get_pointer_pos()] == 1) || !occupied[get_pointer_pos()]) {
                return end();
            }
            else {
                inc();
            }
        }
    }

    bool check(Tkey target) {
        set_index_to(target);

        while (true) {
            if (container[get_pointer_pos()].first == target && occupied[get_pointer_pos()] == 2) {
                return true;
            }
            else if ((container[get_pointer_pos()].first == target && occupied[get_pointer_pos()] == 1) || !occupied[get_pointer_pos()]) {
                return false;
            }
            else {
                inc();
            }
        }
    }

    data_cell*& end() {
        static data_cell* dummy = container + SIZE * sizeof(data_cell);
        return dummy;
    }

    ~hashtable() {
        delete[] container;
    }//D-TOR

private:
    static const unsigned SIZE = 1048576, MOD = SIZE - 1,  /// will work with less ( 1 << 17)
        PRIME1 = 21313, PRIME2 = 19937, mask = 0xFFF00000;

    bool string_hash, int_hash, generic_hash;

    data_cell* pointer, * container;
    int_fast8_t occupied[SIZE];

    _hasher default_hsh;

    unsigned get_pointer_pos() {
        return (pointer - container) / sizeof(data_cell);
    }

    void inc() {
        if (UNLIKELY((pointer += sizeof(data_cell)) == this->end()))
            pointer = container;
    }

    void set_index_to(Tkey target) {
        pointer = container + (default_hsh(reinterpret_cast<char*>(&target), sizeof(Tkey)) & MOD);
    }
};

struct djb2 {
    uint_fast32_t operator() (char *target, size_t bytes) {
        uint_fast32_t hash = 5381;

        for (; bytes; --bytes)
            hash = ((hash << 5) + hash) + *target;

        return hash;
    }
};

template <class TObj, class TKey, class compare_by, class mapper = std::unordered_map<TObj, unsigned>>
class updateable_heap {
    using _elem = std::pair<TObj, TKey>;
public:
    updateable_heap(size_t _size = 1024) : max_size(_size),
        current_bound(1) {
        storage = new _elem[max_size];
    }

    updateable_heap(const updateable_heap<TObj, TKey, compare_by>& target) { *this = target; }

    updateable_heap& operator = (const updateable_heap<TObj, TKey, 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;
        positions = target.positions;
    }

    [[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];
        positions.erase(storage[0].first);
        storage[1] = storage[--current_bound];

        sift_down(1);

        return storage[0];
    }

    [[gnu::hot]] inline void update(_elem target) {
        auto location = positions.find(target.first);

        if (location != positions.end()) {
            if (comparator(storage[location->second].second, target.second)) {
                storage[location->second].second = target.second;
                sift_down(location->second);
            }
            else {
                storage[location->second].second = target.second;
                sift_up(location->second);
            }
        }
        else {
            add(target);
        }
    }

    void run_diagnostic() {
        for (int i = 1; i < current_bound; ++i) {
            std::cout << storage[i].first << " " << storage[i].second << std::endl;
        }
        std::cout << "--------------------------------------\n";
    }

    void integrity_check() {
        for (int i = 2; i < current_bound; ++i) {
            if (comparator(storage[i].second, parent(i).second))
                std::cout << "Structural Integrity failure\n";
        }
    }

    ~updateable_heap() { delete[] storage; }

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

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

        storage[crawler] = aux;
        positions[aux.first] = crawler;
    }

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

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

        storage[crawler] = aux;
        positions[aux.first] = crawler;
    }

    [[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;

    mapper positions;
};

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() {
        if (empty())
            exit(2);
        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)) ||
                 right_son_pos(crawler) == current_bound)) {
                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 first, second;
};

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

std::vector <edge> graph[50010];
int distance[50010], number_of_nodes;
/*
void dijkstra(int nod) {
    heap<edge, edge_comparator> h(250010);

    for (int i = 1; i <= number_of_nodes; ++i)
        distance[i] = INF;

    distance[nod] = 0;
    h.add({ nod, 0 });

    while (!h.empty()) {
        auto current = h.pop();
        if (distance[current.first] != current.second) continue;

        for (auto i : graph[current.first])
            if (distance[i.first] > distance[current.first] + i.second)
                distance[i.first] = distance[current.first] + i.second,
                h.add({ i.first, distance[i.first] });
    }
}
*/

void dijkstra(int nod) {
    updateable_heap<int, int, std::less<int>, hashtable<int, unsigned, djb2>> h(1 + number_of_nodes);

    for (int i = 1; i <= number_of_nodes; ++i)
        distance[i] = INF;

    distance[nod] = 0;
    h.update({ nod, 0 });

    while (!h.empty()) {
        auto current = h.pop();

        if (current.second == INF)
            break;
        for (auto i : graph[current.first])
            if (distance[i.first] > distance[current.first] + i.second)
                distance[i.first] = distance[current.first] + i.second,
                h.update({ i.first, distance[i.first] });
    }
}

int main() {
    parser f("dijkstra.in");
    writer 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;
}