#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){
    int q[50001], qcnt = 0, q_aux[50001], qcnt_aux = 0;
    /// prima oara in coada intra sursa
    q[++qcnt] = 1;
    for(int i = 1; i < n; i++){
        qcnt_aux = 0;
        for(int j = 1; j <= qcnt; j++){
            int k = heads[q[j]];
            while(k){
                int x = q[j], y = lst[k].dest, c = lst[k].cost;
                if(d[y] > d[x] + c){
                    d[y] = d[x] + c;
                    /// la pasul i + 1, bagam intr-o coada la verificat doar nodurile care au fost optimizate la pasul i, astfel eliminand muchiile nenecesare / neproductive
                    q_aux[++qcnt_aux] = y;
                }
                k = _next[k];
            }
        }
        /// formam coada pentru pasul urmator
        for(int j = 1; j <= qcnt_aux; j++)
            q[j] = q_aux[j];
        qcnt = qcnt_aux;
    }
    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;
}