#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
constexpr int INF = 200000000;

int main(){
    int n,m;
    fin>> n>>m;
    vector<vector<pair<int,int>>> lista(n+1);
    for (int i = 0; i<m; i++) {
        int u,v,c;
        fin>>u>>v>>c;
        lista[u].emplace_back(v,c);
    }
    vector<int> dist(n+1, INF);
    vector<int> cnt(n+1, 0);
    vector<bool> inQueue(n + 1, false);
    queue<int> q;

    dist[1] = 0;
    q.push(1);
    inQueue[1] = true;
    bool hasNegativeCycle = false;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;

        for (auto& [v,c] : lista[u]) {
            if (dist[u] != INF) {
                if (dist[v] > dist[u] + c) {
                    dist[v] = dist[u] + c;
                    cnt[v]++;

                    if (cnt[v] >=n) {
                        hasNegativeCycle = true;
                        break;
                    }

                    if (!inQueue[v]) {
                        q.push(v);
                        inQueue[v] = true;
                    }
                }
            }
        }
        if (hasNegativeCycle) break;

    }


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