#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

#define NMAX 50002
#define INF 2000000000

int n, m;
int s[NMAX];

struct muchie
{
    int x, c;
}aux;

vector<muchie> v[NMAX];

bool bellmanford()
{
    for(int nrc=1; nrc<n; ++nrc)
        for(int i=1; i<=n; ++i)
            for(int j=0; j<v[i].size(); ++j)
            {
                if(s[v[i][j].x] > s[i]+v[i][j].c)
                    s[v[i][j].x] = s[i]+v[i][j].c;
            }

    for(int i=1; i<=n; ++i)
        for(int j=0; j<v[i].size(); ++j)
        {
            if(s[v[i][j].x] > s[i]+v[i][j].c)
                return false;
        }
    return true;
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    int x;

    scanf("%d%d", &n, &m);

    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d%d", &x, &aux.x, &aux.c);

        v[x].push_back(aux);
    }

    for(int i=2; i<=n; ++i)
        s[i]=INF;

    if(bellmanford())
    {
        for(int i=2; i<=n; ++i)
            printf("%d ", s[i]);
        printf("\n");
    }else
        printf("Ciclu negativ!\n");

    return 0;
}