#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");
vector <int> A[50001], C[50001];
//vector <int> C[50001];
#define inf 1e9
int d[50001], n, NRV[50001], incoada[50001];
queue <int> q;
int main()
{
    int m, i, x, y, c, p, k, ciclu_negativ,z;
    fi >> n >> m;
    z = 1;
    for( i = 1; i <= m; i++ ){
        fi >> x >> y >> c;
        A[x].push_back(y);
        C[x].push_back(c);
    }
    for( i = 1; i <= n; i++ )
        d[i] = inf;
    d[1] = 0;

    ciclu_negativ = 0;
    q.push(1);
    NRV[1] = 1;
    while( !q.empty() && ciclu_negativ == 0 ){
        k = q.front();
        incoada[k] = 0;
        q.pop();
        for( i = 0; i < A[k].size(); i++ )
            if( d[A[k][i]] > d[k] + C[k][i] ){
                d[A[k][i]] = d[k] + C[k][i];
                if( incoada[A[k][i]] == 0 ){
                    q.push(A[k][i]);
                    incoada[A[k][i]] = 1;
                    NRV[A[k][i]]++;
                    if( NRV[A[k][i]] > n ){
                       ciclu_negativ = 1;
                    }
                }
            }
    }


    if( ciclu_negativ == 1 )
        fo << "Ciclu negativ!";
    else{
        for( i = 2; i <= n; i++ )
            if( d[i] != inf )
                fo << d[i] << " ";
            else
                fo << 0 << " ";
    }
    return 0;
}