#include <fstream>
#include <vector>
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;

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);
        d[i] = inf;
    }

    for( i = 0; i < A[z].size(); i++ )
        d[A[z][i]] = C[z][i];
    d[z] = 0;
    for( p = 1; p < n; p++ )
        for( k = 1; k < n; k++ )
            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];

    ciclu_negativ = 0;
    for( k = 1; k <= n; k++ )
            for( i = 0; i < A[k].size(); i++ )
                if( d[A[k][i]] > d[k] + C[k][i] )
                    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;
}