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

int main() {
    ios::sync_with_stdio(false);

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

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

    vector<tuple<int, int, int>> edges;

    for (int i = 0; i < m; i++) {
        int src, dst, cost;
        fin >> src >> dst >> cost;

        src--;
        dst--;

        edges.push_back({src, dst, cost});
    }

    vector<int> distances(n, INT_MAX >> 1);
    distances[0] = 0;

    for (int i = 0; i < n - 1; i++) {
        for (const auto &[src, dst, cost] : edges) {
            if (distances[dst] > distances[src] + cost) {
                distances[dst] = distances[src] + cost;
            }
        }
    }

    for (const auto &[src, dst, cost] : edges) {
        if (distances[dst] > distances[src] + cost) {
            fout << "Ciclu negativ!\n";
            return 0;
        }
    }

    for (int i = 1; i < n; i++) {
        if (i != 1) {
            fout << ' ';
        }
        fout << distances[i];
    }
    fout << '\n';

    return 0;
}