#include <cstdio>
#include <bitset>
#include <vector>
#include <queue>
#define N  50001
#define M 250001
#define node first
#define cost second
#define INF 0x3f3f3f3f
#define iter vector<pair<int, int> >::iterator

using namespace std;

vector<pair<int, int> > L[N]; // The adjacency list to store the graph
queue<int> Q;   // Holds the nodes which were updated in the previous step
bitset<N> E;    // Checks which nodes are currently in the queue
int CNT[N];     // Checks how often a node ought to be added to the queue
int D[N];       // The approximate distance of the nodes from the source node

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        L[a].push_back(make_pair(b, c));
    }
    
    for (int i = 2; i <= n; ++i)
        D[i] = INF;
    
    bool negativeCycle = false;
    for (Q.push(1), CNT[1] = 1; !Q.empty() && !negativeCycle; Q.pop()) {
        int node = Q.front();
        E[node] = 0;
        for (iter it = L[node].begin(); it != L[node].end(); ++it) {
            int val = D[node] + it -> cost;
            if (val < D[it -> node]) {
                D[it -> node] = val;
                if (CNT[it -> node] == n - 1)
                    negativeCycle = true;
                else {
                    if (!E[it -> node]) {
                        Q.push(it -> node);
                        E[it -> node] = 1;
                    }
                    ++CNT[it -> node];
                }
            }
        }
    }

    if (negativeCycle)
        printf("Ciclu negativ!\n");
    else
        for (int i = 2; i <= n; ++i)
            printf("%d ", (D[i] == INF ? 0 : D[i]));

    return 0;
}