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

#define INF 999999999
#define N 50005

using namespace std;

struct Task {
public:
    void solve() {
        read_input();
        get_result(1);
    }

private:
    int d[N], marked[N], n, m;
    vector<pair<int, int> > adj[N];

    void read_input() {
        ifstream in("bellmanford.in");
        in >> n >> m;

        for (int i = 0; i < m; i++) {
            int start, end, cost;
            in >> start >> end >> cost;
            adj[start].push_back(make_pair(end, cost));
        }

        in.close();
    }

    void get_result(int source) {
        int i;
        ofstream out("bellmanford.out");

        for (i = 0; i <= n; i++) {
            d[i] = INF;
            marked[i] = 0;
        }
        d[source] = 0;
    
        queue<int> q;
        q.push(source);
    
        while (!q.empty()) {
            int currentNode = q.front();
            q.pop();

            for (pair<int, int> node : adj[currentNode]) {
                if (d[node.first] > d[currentNode] + node.second) {
                    d[node.first] = d[currentNode] + node.second;
                    q.push(node.first);
                    marked[node.first]++;
                    if (marked[node.first] == n) {
                        out << "Ciclu negativ!";
                        return;
                    }
                }
            }
        }
    
        for (i = 1; i <= n; i++) {
            if (i != source) {
                if (d[i] == INF) {
                    d[i] = 0;
                }
                out << d[i] << " ";
            }
        }

        out << endl;
        out.close();
    }
};

int main() {
    Task *task = new Task;
    task->solve();
    delete task;
    return 0;
}