#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <queue>
#include <stdio.h>

#define maxN 50005
#define maxM 250005
#define INF 100000000

using namespace std;

int n, m, c, x, y;
bool negativeCyle = false;
bitset<maxN> inQ = false;
vector<pair <int, int> > arr[maxN];
vector<int> cntInQ(maxN, 0), cost(maxN, INF);
queue<int> Q;

void citireMuchii() {
    for(int i = 1; i <= m; ++i) {
        scanf("%d %d %d", &x, &y, &c);
        arr[x].push_back(make_pair(y, c));
    }
}

void afisareMuchii() {
    for(int i = 1; i <= n; ++i) {
        printf("%d: ", i);
        for(int j = 0; (unsigned)j < arr[i].size(); ++j) {
            printf(" %d, c = %d ", arr[i][j].first, arr[i][j].second);
        }
        printf("\n");
    }
}

void BelmanFord(int nodStart) {
    int currElem, newCost, qF;

    Q.push(nodStart);
    inQ[nodStart] = true;
    cntInQ[nodStart] = 1;
    cost[nodStart] = 0;

    while(!Q.empty() && !negativeCyle) {
        qF = Q.front();
        for(int i = 0; (unsigned)i < arr[qF].size(); ++i) {
            currElem = arr[qF][i].first;
            newCost = cost[qF] + arr[qF][i].second;
            if( newCost < cost[currElem] ) {
                cost[currElem] = newCost;
                if(!inQ[currElem]) {
                    if(cntInQ[currElem] > n)
                        negativeCyle = true;
                    else {
                        Q.push(currElem);
                        inQ[currElem] = true;
                        cntInQ[currElem]++;
                    }
                }
            }
        }
        Q.pop();
        inQ[qF] = false;
    }
}

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d %d", &n, &m);
    citireMuchii();
    BelmanFord(1);
    if(!negativeCyle) {
        for(int i = 1; i <= n; ++i)
            printf("%d ", cost[i]);
    } else {
        printf("Ciclu negativ!");
    }
    return 0;
}