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

const int INF=2000000000;
const int NMAX=50005;

vector<pair<int,int>> G[NMAX];
int d[NMAX];
bool inQueue[NMAX];
int cntRelax[NMAX];  
int N, M;

bool bellmanFord(int start) {
    for (int i=1;i<=N;i++) {
        d[i]=INF;
        inQueue[i]=false;
        cntRelax[i]=0;
    }
    queue<int> q;
    d[start]=0;
    q.push(start);
    inQueue[start]=true;
    while (!q.empty()) {
        int nod=q.front();
        q.pop();
        inQueue[nod]=false;
        for (auto &edge : G[nod]) {
            int vecin=edge.first;
            int cost=edge.second;
            if ((d[nod]+cost) < d[vecin]) {
                d[vecin]=d[nod]+cost;
                if (!inQueue[vecin]) {
                    q.push(vecin);
                    inQueue[vecin]=true;
                    cntRelax[vecin]++;
                    if (cntRelax[vecin] >= N) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d %d", &N, &M);
    for (int i=0;i<M;i++) {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        G[x].push_back({y, c});
    }
    bool negCycle=bellmanFord(1);
    if (negCycle) {
        printf("Ciclu negativ!");
    } else {
        for (int i=2;i<=N;i++) {
            if (d[i]==INF)
                printf("0");
            else
                printf("%d", d[i]);

            if (i!=N)
                printf(" ");
        }
    }
    return 0;
}