#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 50000;
const int INF = 2.e9;
struct muchii
{
    int x , y , z;
    muchii(int tx = 0 , int ty = 0 , int tz = 0)
    {
        x = tx;
        y = ty;
        z = tz;
    }
};
muchii v[NMAX + 5];
int d[NMAX + 5];
int main()
{
    freopen("bellmanford.in" , "r" , stdin);
    freopen("bellmanford.out" , "w" , stdout);
    int n , m , x , y , z , i , j , ok;
    scanf("%d%d" , &n , &m);
    for(i = 1 ; i <= m ; i ++)
    {
        scanf("%d%d%d" , &x , &y , &z);
        v[i] = muchii(x , y , z);
    }
    for(i = 2 ; i <= n ; i ++)
        d[i] = INF;
    for(i = 1 ; i < n ; i ++)
        for(j = 1 ; j <= m ; j ++)
            d[v[j].y] = min(d[v[j].y] , d[v[j].x] + v[j].z);
    ok = 1;
    for(j = 1 ; j <= m && ok ; j ++)
        if(d[v[j].y] > d[v[j].x] + v[j].z)
            ok = 0;
    if(ok)
        for(i = 2 ; i <= n ; i ++)
            printf("%d " , d[i]);
    else
        printf("Ciclu negativ!\n");
    return 0;
}