/**
 *  Worg
 */
#include <queue>
#include <bitset>
#include <vector>
#include <fstream>

struct Edge {
    int to;
    int distance;

    Edge(const int& _to, const int& _distance) : to(_to), distance(_distance) {}
};

class Graph {
private:
    int num_nodes;
    std::vector<std::vector<Edge>> adjacency_arrays;
    std::vector<int> enqueue_count;

    inline void enqueue(std::queue<int>& node_queue, std::vector<bool>& in_queue, const int& node) {
        if (!in_queue[node]) {
            node_queue.push(node);
            in_queue[node] = true;
            enqueue_count[node] += 1;

            if (enqueue_count[node] > num_nodes) {
                std::ofstream fout("bellmanford.out");
                fout << "Ciclu negativ!";
                fout.close();
                exit(0);
            }
        }
    }
public:
    static const int MAX_DISTANCE = 1'000'000'000;

    Graph(const int& _num_nodes) : num_nodes(_num_nodes) {
        adjacency_arrays = std::vector<std::vector<Edge>>(num_nodes, std::vector<Edge>());
        enqueue_count = std::vector<int>(num_nodes, 0);
    }

    inline void add_edge(const int& from, const int& to, const int &distance) {
        adjacency_arrays[from].push_back(Edge(to, distance));
    }


    std::vector<int> run_bellman_ford(const int starting_node) {
        std::vector<int> node_distances(num_nodes, MAX_DISTANCE);
        std::queue<int> node_queue;
        std::vector<bool> in_queue(num_nodes, false);

        node_distances[starting_node] = 0;
        enqueue(node_queue, in_queue, starting_node);

        while (!node_queue.empty()) {
            int current_node = node_queue.front();
            node_queue.pop();
            in_queue[current_node] = false;

            for (const auto& edge : adjacency_arrays[current_node]) {
                if (node_distances[current_node] + edge.distance < node_distances[edge.to]) {
                    node_distances[edge.to] = node_distances[current_node] + edge.distance;
                    enqueue(node_queue, in_queue, edge.to);
                }
            }
        }

        return node_distances;
    }
};

int main() {
    const int STARTING_NODE = 0;

    std::ifstream fin("bellmanford.in");
    int num_nodes;
    int num_edges;
    fin >> num_nodes >> num_edges;

    Graph graph(num_nodes);
    for (int i = 0; i < num_edges; i++) {
        int from, to, distance;
        fin >> from >> to >> distance;
        graph.add_edge(from - 1, to - 1, distance);
    }

    std::vector<int> node_distances = graph.run_bellman_ford(STARTING_NODE);
    node_distances.erase(node_distances.begin() + STARTING_NODE);  //  Problem-specific thing

    std::ofstream fout("bellmanford.out");
    for (const auto& distance : node_distances) {
        fout << distance << " ";
    }
    fout.close();
    return 0;
}