#include <cassert>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const int nmax=50000, inf=1<<30;

struct str{
    int x, y;
};

inline str mp(int x, int y){
    str aux;
    aux.x=x; aux.y=y;
    return aux;
}

bool u[nmax+1];
int d[nmax+1], cnt[nmax+1];
queue <int> q;
vector <str> g[nmax+1];

int main(){
    bool neg_cyc;
    int n, m;
    
    assert(freopen("bellmanford.in", "r", stdin));
    assert(scanf(" %d %d ", &n, &m));
    for (; m; --m){
        int x, y, z;

        assert(scanf(" %d %d %d ", &x, &y, &z));
        g[x].push_back(mp(y, z));
    }
    fclose(stdin);

    for (int i=2; i<=n; ++i){
        d[i]=inf;
    }
    neg_cyc=0;
    q.push(1); u[1]=1; 
    cnt[1]=1;
    
    while (!q.empty()&& !neg_cyc){
        int x;

        x=q.front();
        q.pop(); u[x]=0;

        for (vector <str>::iterator it=g[x].begin(); it!=g[x].end(); ++it){
            if (d[it->x]>d[x]+(it->y)){
                d[it->x]=d[x]+(it->y);
                
                if (!u[it->x]){
                    if (cnt[it->x]>=n){
                        neg_cyc=1;
                        break;
                    }else{
                        q.push(it->x); u[it->x]=1; 
                        ++cnt[it->x];
                    }
                }
            }
        }
    }

    assert(freopen("bellmaford.out", "w", stdout));
    if (neg_cyc){
        printf("Ciclu negativ!\n");
    }else{
        for (int i=2; i<=n; ++i){
            printf("%d ", d[i]);
        }
        printf("\n");
    }
    fclose(stdout);

    return 0;
}