#include <iostream>
#include <fstream>
#include <vector>
#define MAX 2100000000

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

struct muchie{
    int vecin, cost;
};
vector<muchie>graf[50005];
int distTo[50005], N, M, x, y, c;

void afis(){
    for(int i = 1 ; i <= N; i++)
        fout << distTo[i] << ' ';
    fout << endl;
}

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++){
        fin >> x >> y >> c;
        muchie m; m.vecin = y; m.cost = c;
        graf[x].push_back(m);
    }

    for(int i = 1; i <= N; i++)
        distTo[i] = MAX;

    distTo[1] = 0;
    for(int j = 1; j < M; j++){
        bool bun = true;
        for(int i = 1; i <= N; i++){
            //cout << i << ' ' << graf[i].size() << endl;

            for(vector<muchie>::iterator it = graf[i].begin(); it != graf[i].end(); ++it){
                //fout << i << endl;
                if(distTo[i] + (*it).cost < distTo[(*it).vecin]){
                    distTo[(*it).vecin] = distTo[i] + (*it).cost;bun = false;}
                    //fout << i << ' ' << (*it).cost << ' ' << distTo[i] << endl;
            }
        }
        if(bun) break;
        //afis();
    }

    for(int i = 1; i <= N; i++)
            for(auto x: graf[i])
                if(distTo[i] + x.cost < distTo[x.vecin]){
                    fout << "Ciclu negativ!";
                    return 0;
                }

    for(int i = 2; i <= N; i++)
        fout << distTo[i] << ' ';


    return 0;
}