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

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

    int n, m;
    fin >> n >> m;

    vector<int> x(m), y(m), c(m);
    for (int i = 0; i < m; i++) {
        fin >> x[i] >> y[i] >> c[i];
    }

    vector<long long> dist(n + 1, LLONG_MAX);
    dist[1] = 0;

    bool negativeCycle = false;

    // facem N-1 runde de relaxare
    for (int pas = 1; pas <= n - 1; pas++) {
        for (int i = 0; i < m; i++) {
            if (dist[x[i]] != LLONG_MAX && dist[x[i]] + c[i] < dist[y[i]]) {
                dist[y[i]] = dist[x[i]] + c[i];
            }
        }
    }

    // runda in plus: daca mai putem relaxa, avem ciclu negativ
    for (int i = 0; i < m; i++) {
        if (dist[x[i]] != LLONG_MAX && dist[x[i]] + c[i] < dist[y[i]]) {
            negativeCycle = true;
        }
    }

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

    return 0;
}