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

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

vector<long long> d(50001, LLONG_MAX);
vector<vector<pair<int,long long>>> a(50001);
vector<int> fr(50001);
queue<int> q;

int n, m;
int main(){
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x, y;
        long long cost;
        fin >> x >> y >> cost;
        a[x].push_back({y, cost});
    }
    
    bool f = 0;    
    d[1] = 0;
    q.push(1);
    fr[1] = 1;
    while(!q.empty() && !f){
        int i = q.front();
        q.pop();
        for(pair<int,int> x : a[i]){
            int j = x.first;
            int cost = x.second;
            if(fr[j]+1 == n){
                f = 1;
                break;
            }else if(d[j] > d[i] + cost){
                d[j] = d[i] + cost;
                fr[j]++;
                q.push(j);
            }
        }
    }
    
    
    if(f){
        fout << "Ciclu negativ!";
    }else{
        for(int i = 2; i <= n; ++i)
            fout << d[i] << " ";
    }
    
}