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

using namespace std;

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

vector<pair<int, int> > v[50002];

queue<int> q;

const int INF = 3001;

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

bool ok = false;

int main()
{

    fin>>n>>m;

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

        fin>>a>>b>>c;

        v[a].push_back(make_pair(b, c));

        d[i] = INF;

    }

    d[1] = 0; q.push(1); inQ[1] = true;


    while (!q.empty()) {

        a = q.front();
        q.pop();
        inQ[a] = false;

        for (int i=0; i<v[a].size(); i++) {

            b = v[a][i].first;
            c = v[a][i].second;

            if (d[b] > d[a] + c) {
                d[b] = d[a] + c;

                if (inQ[b] == false) {
                    q.push(b);
                    inQ[b] = true;
                }

            }

        }

    }

    for (int i=0; i<v[1].size(); i++) {

        b = v[1][i].first;
        c = v[1][i].second;

        if (d[b] > d[a] + c) {
            d[b] = d[a] + c;

            ok = true;
            break;

        }

    }



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


    return 0;
}