#include <bits/stdc++.h>

using namespace std;

#define INF (1 << 30)
const int NMAX = 5 * 1e4 + 5;

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

int N, M;

struct Edge {
    int x;
    int y;
    int w;

    Edge(int _x, int _y, int _w) : x(_x), y(_y), w(_w) {}
};
vector<Edge> edges;

bool bellman_ford(int src, vector<int>& d) {
    d[src] = 0;

    int i;

    for (i = 1; i < N; ++i) {
        for (auto e : edges) {
            if (d[e.y] > d[e.x] + e.w) {
                d[e.y] = d[e.x] + e.w;
            }
        }
    }

    // check for negative cycles
    for (auto e : edges) {
        if (d[e.y] > d[e.x] + e.w) {
            // can update the distance
            //   -> negative cycle
            return false;
        }
    }

    for (int x = 1; x <= N; ++x) {
        if (d[x] == INF) {
            d[x] = 0;
        }
    }

    return true;
}

int main() {
    int i, x, y, w;

    fin >> N >> M;

    for (i = 1; i <= M; ++i) {
        fin >> x >> y >> w;

        edges.push_back(Edge(x, y, w));
    }

    vector<int> d(N + 1, INF);
    bool ok = bellman_ford(1, d);

    if (!ok) {
        fout << "Ciclu negativ!\n";
    } else {
        for (x = 2; x <= N; ++x) {
            fout << d[x] << " ";
        }
        fout << "\n";
    }

    return 0;
}