//
// Created by h4rapa1b on 11/25/25.
//
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

const int INF = 2000000000;
int main() {
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    int n, m;
    fin >> n >> m;

    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        fin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    // init vector de distante
    vector<int> dist(n + 1, INF);
    dist[1] = 0;

    vector<bool> inQueue(n + 1, false);
    vector<int> counter(n + 1, 0);

    queue<int> que;
    que.push(1);
    inQueue[1] = true;

    bool hasNegCycle = false;
    // algoritmul Bellman-Ford cu optimizare spfa
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        // nodul nu mai e in coada, dar poate reveni
        inQueue[u] = false;

        for (auto &e: graph[u]) {
            int v = e.first;
            int w = e.second;

            // verif daca am gasit o dist mai buna
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;

                // verif ciclu negativ
                counter[v]++;
                if (counter[v] >= n) {
                    hasNegCycle = true;
                    break;
                }

                if (!inQueue[v]) {
                    que.push(v);
                    inQueue[v] = true;
                }
            }
        }

        if (hasNegCycle) break;
    }

    if (hasNegCycle) {
        fout<<"Ciclu negativ!";
    } else {
        for (int i = 2; i <= n; ++i) {
            if (dist[i] == INF) {
                fout << 0 << " ";
            } else {
                fout << dist[i] << " ";
            }
        }
    }

    fin.close();
    fout.close();
    return 0;
}