#include <bits/stdc++.h>
using namespace std;

const int NMAX = 50005,
           INF = 1e9;

struct PII {
    int u, c;

    inline PII() { }
    inline PII(int _u, int _c) {
        u = _u;
        c = _c;
    }
};

vector<PII> g[NMAX];
queue <int> q;

int  ant[NMAX],
     viz[NMAX];
bool inq[NMAX];

void bford(int n) {
    int  c;  //current nod
    bool nc; //negative cycle flag

    q.push(1);
    ant[1] = 0;
    viz[1] = 1;
    nc     = false;

    while(!q.empty() && !nc) {
        c      = q.front();
        inq[c] = false;
        q.pop();

        for(auto i:g[c]) if(!inq[i.u] && i.c+ant[c] < ant[i.u]) {
            ant[i.u] = i.c + ant[c];
            viz[i.u]++;
            q.push(i.u);

            if(viz[i.u]>n) {
                nc = true;
                break;
            }
        }
    }

    if(nc) {
        printf("Ciclu negativ!\n");
    }
    else {
        for(int i=2; i<=n; ++i)
            printf("%d ",ant[i]);
        printf("\n");
    }
}

int main(void) {
    freopen("bellmanford.in",  "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    memset(ant, 0x3f, sizeof(ant));
    int n, m, x, y, c;

    scanf("%d%d",&n,&m);
    for(int i=0; i<m; ++i) {
        scanf("%d%d%d",&x,&y,&c);
        g[x].push_back(PII(y, c));
    }

    bford(n);

    fclose(stdin);
    fclose(stdout);
    return 0;
}