#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip>
#include <utility>
#include <map>
#include <algorithm>

const std::string InputFile = "bellmanford.in";
const std::string OutputFile = "bellmanford.out";
const int INF = 0x7fffffff;

class Edge {
public:
    int destination, cost;
    Edge(int dest, int c) : destination(dest), cost(c) {
    }
    Edge() : destination(-1), cost(-1) {
    }
};

typedef std::vector<std::vector<Edge>> Graph;

std::istream& operator >> (std::istream& stream, Graph& graph) {
    int N, M;
    stream >> N >> M;
    graph.resize(N+1);
    for (register int i = 0; i < M; i++) {
        int source, destination, cost;
        stream >> source >> destination >> cost;
        graph[source].push_back(Edge(destination,cost));
    }
    return stream;
}

std::ostream& operator << (std::ostream& stream, std::vector<int>& v) {
    for (auto it = v.begin()+2; it < v.end(); ++it)
        stream << ((*it) == INF ? 0 : (*it)) << ' ';
    return stream;
}

std::vector<int> bellman_ford(const Graph& graph, int source, bool& found_neg_cycle) {
    std::vector<int> distances(graph.size(), INF);
    std::vector<int> visited(graph.size(), 0);
    std::queue<int> queue;

    distances[source] = 0;
    queue.push(source);

    while(!queue.empty()) {
        int node = queue.front();
        queue.pop();
        
        for (auto it = graph[node].begin(); it < graph[node].end(); ++it)
            if (distances[it->destination] > distances[node] + it->cost) {
                distances[it->destination] = distances[node] + it->cost;
                queue.push(it->destination);
                visited[it->destination]++;
                if (visited[it->destination] == static_cast<int>(graph.size()) ) {
                    found_neg_cycle = true;
                    return distances;
                }
            }
    }
    return distances;
}

int main(void) {
    std::ifstream fin(InputFile);
    std::ofstream fout(OutputFile);
    Graph graph;
    std::vector<int> distances;
    bool found_neg_cycle = false;

    fin >> graph;
    distances = bellman_ford(graph, 1, found_neg_cycle);
    
    if (found_neg_cycle)
        fout << "Ciclu negativ!\n";
    else
        fout << distances << '\n';    

    fin.close();
    fout.close();
    return 0;
}