#include <bits/stdc++.h>
using namespace std;
struct edge{
    int dest, cost;
};

int heads[50001], cnt;

edge lst[250001];
int _next[250001];

int d[50001];

bool bellmanford(int s, int n){
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= n; j++){
            int k = heads[j];
            while(k){
                int x = j, y = lst[k].dest, c = lst[k].cost;
                if(d[y] > d[x] + c){
                    d[y] = d[x] + c;
                }
                k = _next[k];
            }
        }
    }
    for(int j = 1; j <= n; j++){
        int k = heads[j];
        while(k){
            int x = j, y = lst[k].dest, c = lst[k].cost;
            if(d[y] > d[x] + c){
                return false;
            }
            k = _next[k];
        }
    }
    return true;
}

int main() {
    int n, m, x, y, c;
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d", &x, &y, &c);
        ++cnt;
        _next[cnt] = heads[x];
        heads[x] = cnt;
        lst[cnt] = {y, c};
    }
    for(int i = 2; i <= n; i++)
        d[i] = INT32_MAX / 2 - 1;
    bool sol = bellmanford(1, n);
    if(sol){
        for(int i = 2; i <= n; i++)
            printf("%d ", d[i]);
        return 0;
    }
    printf("Ciclu negativ!");

    return 0;
}