#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int nmax = 5e4;
int n, m;
struct muchie {
    int first, second, cost;
};
vector< muchie > muchii;

void citire() {
    fin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int x, y, c;
        fin >> x >> y >> c;
        muchii.push_back({x, y, c});
    }
}

int d[nmax + 1];
const int inf = 999999999;
void bellmanford(int start) {
    for(int i = 1; i <= n; i ++) {
        d[i] = inf;
    }

    d[start] = 0;

    for(int i = 1; i <= n - 1; i ++) {
        for(auto &m : muchii) {
            int u = m.first, v = m.second, cost = m.cost;

            if (d[u] != inf && d[u] + cost < d[v]) {
                d[v] = d[u] + cost;
            }
        }
    }


    for(auto &m : muchii) {
        int u = m.first, v = m.second, cost = m.cost;

        if (d[u] != inf && d[u] + cost < d[v]) {
            fout << "Ciclu negativ!";
            return;
        }
    }


    for(int i = 1; i <= n; i ++) {
        if(i == start) 
            continue;
            
        if(d[i] == inf) {
            fout << "0 ";
        }
        else {
            fout << d[i] << " ";
        }
    }
}

int main() {
    citire();
    bellmanford(1);
    return 0;
}