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

const int INF = 1e9;

struct Edge {
    int x, y, cost;
};

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

    int N, M;
    fin >> N >> M;

    vector<Edge> edges(M);

    for (int i = 0; i < M; i++)
        fin >> edges[i].x >> edges[i].y >> edges[i].cost;

    vector<int> dist(N + 1, INF);
    dist[1] = 0;

    // Bellman-Ford: relax all edges N-1 times
    for (int i = 1; i <= N - 1; i++) {
        bool changed = false;
        for (const auto &e : edges) {
            if (dist[e.x] < INF && dist[e.x] + e.cost < dist[e.y]) {
                dist[e.y] = dist[e.x] + e.cost;
                changed = true;
            }
        }
        if (!changed) break; // optimization
    }

    // check for negative cycle
    for (const auto &e : edges) {
        if (dist[e.x] < INF && dist[e.x] + e.cost < dist[e.y]) {
            fout << "Ciclu negativ!";
            return 0;
        }
    }

    // output distances (ignore dist[1])
    for (int i = 2; i <= N; i++) {
        if (dist[i] == INF) fout << "0";
        else fout << dist[i];
        if (i != N) fout << " ";
    }

    return 0;
}