#include <bits/stdc++.h>
using namespace std;

const int kNmax = 50005;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int main() {
    int n, m, flag = 0;
    vector<pair<int, int> > adj[kNmax];
    fin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int x, y, w;
        fin >> x >> y >> w;
        adj[x].push_back({y, w});
    }

    vector<int> d(n + 1, numeric_limits<int>::max());
    d[1] = 0;

    for (int i = 0; i < n - 1; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (auto node : adj[j]) {
                if (d[node.first] > d[j] + node.second && d[j] != numeric_limits<int>::max()) {
                    d[node.first] = d[j] + node.second;
                }
            }
        }
    }

    for (int j = 1; j <= n; ++j) {
        for (auto node : adj[j]) {
            if (d[node.first] > d[j] + node.second) {
                flag = 1;
            }
        }
    }

    if (flag) {
        fout << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= n; ++i) {
            fout << d[i] << " ";
        }
    }

    return 0;
}