#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
#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;
};

template <typename Tkey, typename Tinfo, typename comparator, typename infinitum>
class fibonacci_heap {
public:
    struct node {
        node() { }

        node(Tinfo _info, Tkey _key) : key(_key), info(_info) {
            after = nullptr;
            before = nullptr;
            rank = 0;
            state = false;
            child = nullptr;
            parent = nullptr;
        }

        Tkey key;
        Tinfo info;
        unsigned rank;
        bool state;
        node* child, * after, * before, * parent;
    };

    fibonacci_heap(size_t _size = 1024) {
        max_size = _size;
        current_size = 0;
        A = new node * [max_size * sizeof(node*)];
        for (unsigned i = 0; i < max_size; ++i) {
            A[i] = nullptr;
        }
        _root = nullptr;
    }

    node* make_item(Tinfo info, Tkey v) {
        return new node(info, v);
    }

    bool empty() { return (current_size == 0); }

    void add(Tinfo _a, Tkey _b) {
        root() = meld(make_item(_a, _b), root());
    }

    void add(node* a) {
        root() = meld(a, root());
    }

    node pop_node(node* x) {
        decrease_key(x, -1);
        return pop();
    }

    node pop() {
        auto x = root()->child,
             retval = *root(),
             to_be_deleted = root();
        unsigned max_rank = 0;
        root() = x;

        while (x != nullptr) {
            auto y = x;
            x = x->after;

            while (A[y->rank] != nullptr) {
                y = link(y, A[y->rank]);
                A[y->rank] = nullptr;

                if (++(y->rank) == max_size) {
                    max_size <<= 1;
                    auto dummy = new node * [max_size];
                    memcpy(dummy, A, max_size / 2 * sizeof(node*));
                    for (unsigned i = max_size / 2; i < max_size; ++i)
                        dummy[i] = nullptr;
                    delete[] A;
                    A = dummy;
                }
            }

            A[y->rank] = y;
            if (y->rank > max_rank)
                max_rank = y->rank;
        }
        
        for (unsigned i = 0; i <= max_rank; ++i) {
            if (A[i] != nullptr) {
                if (x == nullptr)
                    x = A[i];
                else
                    x = link(x, A[i]);
                A[i] = nullptr;
            }
        }

        --current_size;
        delete to_be_deleted;
        return retval;
    }

    node* top() {
        return root();
    }

    node* decrease_key(node* x, Tkey v) {
        x->key = v;
        if (x == root())
            return root();
        root()->state = false;
        decrease_ranks(x);
        cut(x);
        return link(x, root());
    }

    ~fibonacci_heap() {
        while (!empty()) {
            pop();
        }
        delete[] A;
    }

private:
    node* meld(node* g, node* h) {
        ++current_size;
        if (g == nullptr) return h;
        if (h == nullptr) return g;
        return link(g, h);
    }

    node* link(node* x, node* y) {
        if (!is_less(x->key, y->key)) {
            add_child(x, y);
            return y;
        }
        else {
            add_child(y, x);
            return x;
        }
    }

    void add_child(node* x, node* y) {
        if (x == root())
            root() = y;
        x->parent = y;
        node* z = y->child;
        x->before = nullptr;
        x->after = z;
        if (z != nullptr) {
            z->before = x;
        }
        y->child = x;
    }

    void cut(node* x) {
        node* y = x->parent;
        if (y->child == x) {
            y->child = x->after;
        }
        if (x->before != nullptr) {
            x->before->after = x->after;
        }
        if (x->after != nullptr) {
            x->after->before = x->before;
        }
    }

    void decrease_ranks(node* y) {
        do {
            y = y->parent;
            if (y->rank > 0) {
                y->rank--;
            }
            y->state = !y->state;
        } while (y->state == false);
    }

    node*& root() { return _root; }

    node* _root, ** A;
    size_t current_size, max_size;
    comparator is_less;
    infinitum INF;
};

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;

class infinitum {
    inline int operator()() {
        return -1;
    }
};

void dijkstra(int nod) {
    fibonacci_heap<int, int, std::less<int>, infinitum> h;
    std::vector<bool> vaz(50010);

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

    distance[nod] = 0;
    h.add(nod, 0);
    
    for (int i = 0; i < number_of_nodes && !h.empty(); ++i) {
        auto current = h.pop();
        while (!h.empty() && vaz[current.info])
            current = h.pop();

        vaz[current.info] = true;

        for (auto i : graph[current.info])
            if (distance[i.first] > distance[current.info] + i.second)
                distance[i.first] = distance[current.info] + i.second,
                h.add(i.first, distance[i.first]);
    }
    /*
    while (!h.empty()) {
        auto current = h.pop();
        if (distance[current.info] != current.key) continue;

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


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