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

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

struct muchie{
    int x, y, cost;
};

vector<long long> d(50001, LLONG_MAX);

int n, m;
int main(){
    fin >> n >> m;
    vector<muchie> a(m+1);
    for(int i = 1; i <= m; ++i)
        fin >> a[i].x >> a[i].y >> a[i].cost;
        
    d[1] = 0;
    for(int i = 1; i <= n-1; ++i)
        for(int j = 1; j <= m; ++j)
            if(d[a[j].x] != LLONG_MAX && d[a[j].y] > d[a[j].x] + a[j].cost)
                d[a[j].y] = d[a[j].x] + a[j].cost;
    bool f = 0;
    for(int i = 2; i <= n && !f; ++i)
        if(d[i] == LLONG_MAX) f = 1;
    
    if(f){
        fout << "Ciclu negativ!";
    }else{
        for(int i = 2; i <= n; ++i)
            fout << d[i] << " ";
    }
    
}