#include <bits/stdc++.h>
#include <fstream>
using namespace std;

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

#define inf 1e9

struct mch {
    int v, cost;

    mch(int v, int c) : v(v), cost(c) {}
};

vector<vector<mch>> graf;
vector<int> d, tata, ldr;
vector<bool> viz;
queue<int> q;
bool hasLoop;

void bellmanFord(int n, int s) {
    d.assign(n, inf); tata.assign(n, 0); viz.assign(n, false); ldr.assign(n, 0);
    d[s] = 0; q.push(s); viz[s] = true; hasLoop = false;


    while(!q.empty() && !hasLoop) {
        int u = q.front(); q.pop();
        viz[u] = false;

        for (mch& m : graf[u]) {
            if (d[u] != inf && d[m.v] > d[u] + m.cost) {
                ldr[m.v] = ldr[u] + 1;
                d[m.v] = d[u] + m.cost;
                tata[m.v] = u;
                if (!viz[m.v]) {
                    q.push(m.v);
                    viz[m.v] = true;
                }

                if (ldr[m.v] >= n) { hasLoop = true; break; }
            }
        }
    }
}

int main() {
    int n, m; fin >> n >> m;
    graf.resize(n);

    for (int i = 0; i < m; i++) {
        int x, y, c; fin >> x >> y >> c; x--; y--;
        graf[x].push_back(mch(y, c));
    }

    bellmanFord(n, 0);

    if (hasLoop) { fout << "Ciclu negativ!"; }
    else {
        for (int i = 1; i < n; i++) {
            fout << d[i] << ' ';
        }
    }

    return 0;
}