#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50010;
int DP[MAXN];
struct Edge{
    int from, to, dist;
};
vector<Edge> V;
int N, M;

int main() {

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

    fin >> N >> M;
    for (int i = 1; i <= M;i++) {
        int from, to , dist;
        fin >> from >> to >> dist;
        V.push_back({from, to , dist});
    }

    for (int i = 1; i <= N;i++) DP[i] = 1e9;
    DP[1] = 0;
    for (int i = 1; i <= N;i++) {
        for (auto edge: V) {
            if (DP[edge.from] + edge.dist < DP[edge.to]) {
                DP[edge.to] = DP[edge.from] + edge.dist;
            }
        }
    }

    for (int i = 1; i <= N;i++) {
    for (auto edge: V) {
        if (DP[edge.from] + edge.dist < DP[edge.to]) {
            cout << "Cicle negativ!";
            return 0;
            }
        }
    }

    for (int i = 2; i <= N;i++) cout << DP[i] << " ";

    return 0;
}