#include <bits/stdc++.h>

using namespace std;

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

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

int N, M;
vector<pii> adj[NMAX];

bool bellman_ford(int src, vector<int>& d) {
    queue<int> q;
    vector<int> ct_q(N + 1, 0);
    vector<bool> in_q(N + 1, false);

    d[src] = 0;
    q.push(src);
    in_q[src] = true;

    while (!q.empty()) {
        int x = q.front();

        q.pop();
        in_q[x] = false;

        for (auto p : adj[x]) {
            int y = p.first;
            int w = p.second;

            if (d[y] > d[x] + w) {
                d[y] = d[x] + w;

                if (!in_q[y]) {
                    if (ct_q[y] > N) {
                        return false;
                    } else {
                        in_q[y] = true;
                        q.push(y);
                        ct_q[x]++;
                    }
                }
            }
        }
    }

    // no negative cycles found
    return true;
}

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

    fin >> N >> M;

    for (i = 1; i <= M; ++i) {
        fin >> x >> y >> w;
        adj[x].push_back({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) {
            if (d[x] == INF) {
                fout << 0 << " ";
            } else {
                fout << d[x] << " ";
            }
        }
        fout << "\n";
    }

    return 0;
}