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

using namespace std;

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

struct wEdge {

    int x;
    int y;
    int w;

};

vector<wEdge> v;

const int INF = 3001;

int n, m, a, b, c, d[50002];

wEdge z;

bool ok = false;

int main()
{

    fin>>n>>m;

    for (int i=1; i<=m; i++) {

        fin>>a>>b>>c;

        z.x = a;
        z.y = b;
        z.w = c;

        v.push_back(z);

        d[i] = INF;

    }

    d[1] = 0;

    for (int i=1; i<=n; i++) {
        for (int j=0; j<v.size(); j++) {

            a = v[j].x;
            b = v[j].y;
            c = v[j].w;

            if (i == n and d[b] > d[a]+c) {
                ok = true;
                break;
            }

            d[b] = min(d[b], d[a]+c);
        }
    }

    if (ok) {
        fout<<"Ciclu negativ!\n";
    }
    else {
        for (int i=2; i<=n; i++) {
            fout<<d[i]<<" ";
        }
    }


    return 0;
}