#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const long long INF = 1e15;

struct Edge {
    int from, to;
    int cost;
};

int main() {
    int n, m;
    fin >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        fin >> edges[i].from >> edges[i].to >> edges[i].cost;
    }
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;
    for (int i = 1; i <= n - 1; i++) {
        for (int j = 0; j < m; j++) {
            int u = edges[j].from;
            int v = edges[j].to;
            int c = edges[j].cost;
            if (dist[u] != INF && dist[u] + c < dist[v]) {
                dist[v] = dist[u] + c;
            }
        }
    }
    bool negative_cycle = false;
    for (int j = 0; j < m; j++) {
        int u = edges[j].from;
        int v = edges[j].to;
        int c = edges[j].cost;
        if (dist[u] != INF && dist[u] + c < dist[v]) {
            negative_cycle = true;
            break;
        }
    }

    if (negative_cycle) {
        fout << "Ciclu negativ!\n";
    } else {
        for (int i = 2; i <= n; i++) {
            if (dist[i] == INF) fout << 0 << " ";
            else fout << dist[i] << " ";
        }
        fout << "\n";
    }
    return 0;
}