#include <cstdio>
#include <queue>
#include <algorithm>

#define FORIT(it, v) for(vector< pair< int, int> >::iterator it = (v).begin(); it != (v).end(); ++ it)

#define x first
#define y second
#define INF 1 << 30
#define NMAX 250007

using namespace std;

queue < int > q;
vector< pair< int, int> > v[NMAX];

int Viz[NMAX], D[NMAX], ciclu[NMAX];
int n, c, m;

void bellman(){
    D[1] = 0;
    q.push(1);
    Viz[1] = 0;
    while(! q.empty() && c == 0){
        int Nod = q.front();
        Viz[Nod] = 0;
        q.pop();
        FORIT(it, v[Nod])
            if(D[it->x] > D[Nod] + it->y){
                D[it->x] = D[Nod] + it->y;
                if(!Viz[it->x]){
                    q.push(it->x);
                    Viz[it->x] = 1;
                    ++ ciclu[it->x];
                    if(ciclu[it->x] > n){
                        c = 1;
                        break;
                    }
                }
            }
    }
}

int main(){
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        v[x].push_back(make_pair(y, c));
    }
    for(int i = 1; i <= n; ++i)
        D[i] = INF;
    bellman();
    if(c == 0)
        for(int i = 2; i <= n; ++i)
            printf("%d ", D[i]);
    else
        printf("Ciclu negativ!\n");
    return 0;
}