#include <cstdio>
#include <cstring>
#include <cstdlib>
// ATENTIE LA CITIRE!
#include <vector>
#include <queue>
#define f "bellmanford.in"
#define g "bellmanford.out"
#define nmax 50001
#define inf 0x3f3f3f

using namespace std;

vector < pair<int, int> > gf[nmax];
queue<int> Q;
int d[nmax], viz[nmax], c_neg[nmax], n, m;
bool ciclu_negativ=false;

void bellman_ford(){
    memset(d, inf, sizeof(d));
    viz[1]=1;
    d[1]=0;

    for(Q.push(1); Q.size() && !ciclu_negativ; Q.pop()){
        int nod = Q.front();
        viz[nod]=0;
        for(vector< pair<int, int> >::iterator it=gf[nod].begin(); it!=gf[nod].end(); it++){
            int y = it->first;
            int c = it->second;
            if (d[y] > d[nod] + c){
                d[y] = d[nod] + c;
                if(viz[y] == 0){
                    if(c_neg[y] > n)
                        ciclu_negativ=true;
                    else {Q.push(y);
                    c_neg[y]++;
                    viz[y]=1;
                    }
                }
            }
        }
    }
}

int main(){
    freopen(f, "r", stdin);
    freopen(g, "w", stdout);
    scanf("%d %d\n", &n, &m);
    for(int i=1; i<=m; i++){
        int x, y, c;
        scanf("%d %d %d\n", &x, &y, &c);
        gf[x].push_back(make_pair(y,c));
    }
    bellman_ford();
    if (!ciclu_negativ)
        for(int i=2; i<=n; i++)
            if (d[i] >= inf) printf("0");
            else printf("%d ",d[i]);
    else printf("Ciclu negativ!");

    return 0;
}