#include <fstream>
#include <iostream>
#include <climits>
#define mmax 250005
#define nmax 50005
#define oo 1000000000

using namespace std;

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

struct edge{
    int x, y, c;
}v[mmax];

int n, m, dist[nmax], k;

void init(){
    dist[1] = 0;
    for(int i = 2; i <= n; i++)
        dist[i] = oo;
}

void read(){
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
        fin >> v[i].x >> v[i].y >> v[i].c;
}

void relax(int i){
    if(dist[v[i].y] > dist[v[i].x] + v[i].c){
        dist[v[i].y] = dist[v[i].x] + v[i].c;
        if(k == 1){
            fout << "Ciclu negativ!";
            k = 2;
            return;
        }
    }
}

void print(){
    for(int i = 2; i <= n; ++i)
        fout << dist[i] << " ";
}

void bellmanford(){
    init();
    for(int j = 1; j <= n - 1; ++j)
        for(int i = 1; i <= m; ++i)
            relax(i);
    k = 1;
    for(int i = 1; i <= m; ++i){
        relax(i);
        if(k == 2)
            break;
    }
    if(k == 1)
        print();
}

int main(){

    read();
    bellmanford();
    fin.close();
    fout.close();
    return 0;
}