#include <bits/stdc++.h>
#define INF 7654321

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

struct cv {
    int nodeA;
    int nodeB;
    int cost;
};

int N,M;

forward_list<cv> Edges;
vector<int> C;

int main() {
    fin >> N >> M;
    C.assign(N+1,INF);
    C[1] = 0;
    for (int i = 1; i <= M; i++) {
        int nodeA,nodeB,cost;
        fin >> nodeA >> nodeB >> cost;
        Edges.push_front({nodeA,nodeB,cost});
    }
    for (int i = 1; i < M; i++) {
        for (const cv& edge : Edges) {
            if (C[edge.nodeA] + edge.cost < C[edge.nodeB]) {
                C[edge.nodeB] = C[edge.nodeA] + edge.cost;
            }
        }
    }
    for (int i = 0; i < M-1; i++) {
        for (const cv& edge : Edges) {
            if (C[edge.nodeA] + edge.cost < C[edge.nodeB]) {
                fout << "Ciclu negativ!";
                return 0;
            }
        }
    }
    for (int i = 2; i <= N; i++) {
        fout << C[i] << ' ';
    }
    return 0;
}